JAVA, DFS, backtracking


  • 1
    S
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<String>();
        List<String> cur = new ArrayList<String>();
        if (s == null) return res;
        helper(res, cur, s, 0, 0);
        return res;
    }
    public void helper(List<String> res, List<String> cur, String s, int start, int count) {
        if (count == 4) {
            if (start == s.length()) {
                StringBuilder sb = new StringBuilder();
                for(int i = 0; i<cur.size(); i++) {
                    String fraction = cur.get(i);
                    if(fraction.length() > 1 && fraction.charAt(0) == '0') return;
                    if(Integer.parseInt(fraction) > 255) return;
                    sb.append(cur.get(i) + '.');
                }
                sb.deleteCharAt(sb.length()-1);
                res.add(sb.toString());
            }
            return;
        }
        for (int l=1; l<=3; l++) {
            if (start + l <= s.length()) {
                cur.add(s.substring(start, start+l));
                helper(res, cur, s, start+l, count+1);
                cur.remove(cur.size()-1);
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.