93. Restore IP Addresses

    /*
     * 93. Restore IP Addresses 
     * 2015.12.16 by Mingyang
     * 这里不用StringBuffer因为我们最后要检查每一小块string到底是否符合要求
     * 1.长度标准：无（固定）
     * 2.可选的范围：从start开始到最后一个
     * 3.往前走一步：stringbuffer 变成string跟前面的相加成为一个新的string，然后start加1表示从下一位加起，然后count也减一个
     * 4.后退一步：不用，因为传进去是string，不会对当前状态进行影响
     * 5.特别的case：count小于等于0
     * 6.关于重复：无
     */
    public static List<String> restoreIpAddresses1(String s) {
        List<String> res = new ArrayList<String>();
        dfs(res, s, 0, "", 4);
        return res;
    }
    public static void dfs(List<String> res, String s, int start, String item,
            int count) {
        if (start == s.length() && count == 0) {
            res.add(item);
            return;
        }
        if (count <= 0) {
            return;
        }
        StringBuffer sb = new StringBuffer();
        for (int i = start; i < s.length(); i++) {
            sb.append(s.charAt(i));
            if (isValid(sb.toString())) {
                dfs(res, s, i + 1, item.isEmpty() ? (sb.toString())
                        : (item + '.' + sb.toString()), count - 1);
            } else {
                return;
    // 为什么需要写这个呢，因为这个可以防止多余的计算，比如数字太大2552551113，会让下面的isValid失效，就是省去多余的
            }
        }
    }
    public static boolean isValid(String s) {
        if (s.charAt(0) == '0')
            return s.equals("0"); // 如果以0开头的，必须要检查是否等于001，011等不合格的，若开头为0，整个数必须为0
        int num = Integer.parseInt(s);
        if (num <= 255 && num > 0)
            return true;
        else
            return false;
    }
    // 如果用原来的方法传StringBuffer思路也是一样的，不过注意加.的顺序和return出来以后remove的index
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<String>();
        if (s == null || s.length() < 4 || s.length() > 12)
            return res;
        StringBuilder sb = new StringBuilder();
        helper(0, s, 1, sb, res);
        return res;
    }
    public void helper(int start, String s, int section, StringBuilder sb,
            List<String> res) {
        if (section > 4) {
            if (start >= s.length())
                res.add(sb.toString());
            return;
        }
        if (start >= s.length())
            return;
        int maxNum = (s.charAt(start) == '0') ? 1 : 3;
        for (int i = start; i < s.length() && i < start + maxNum; i++) {
            if (Integer.parseInt(s.substring(start, i + 1)) <= 255) {
                if (section > 1)
                    sb.append('.');
                sb.append(s.substring(start, i + 1));
                helper(i + 1, s, section + 1, sb, res);
                sb.delete(sb.length() - (i + 1 - start), sb.length());
                if (section > 1)
                    sb.deleteCharAt(sb.length() - 1);
            }
        }
    }