Share My backtrack Solution


  • 0
    C
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        // illegal answer
        if (s.length() > 12) {
            return res;
        }
        backTrack(res, s, 0, 0, new StringBuilder());
        return res;
    }
    
    // i is the current index of the s
    // section: indicates the current section, there are total 4 section
    // temp: temperary string, the candidate
    public void backTrack(List<String> res, String s, int i, int section, StringBuilder temp) {
        if (i == s.length()) {
            if (section == 4)
                res.add(temp.toString().substring(0, temp.length() - 1));
            return;
        }
        if (s.length() - i > (4 - section) * 3) {
            return;
        }
        
        
        if (s.charAt(i) == '0') {
        	StringBuilder next = new StringBuilder(temp);
            next.append("0.");
            backTrack(res, s, i + 1, section + 1, next);
            return;
        }
        for (int j = i; j < s.length() && j < i + 3; j++) {
            if (Integer.valueOf(s.substring(i, j + 1)) <= 255) {
                StringBuilder next = new StringBuilder(temp);
                next.append(s.substring(i, j + 1) + ".");
                backTrack(res, s, j + 1, section + 1, next);
            }
        }
    }

Log in to reply
 

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