Java backtracking using StringBuilder with pruning


  • 0
    Y

    This is a typical backtracking problem with a few special cases to consider due to IP address rules.
    First, the total length of digit should not exceed 12. Second, four parts in total separated by "." and each part should be value in the range of 0 ~ 255. Therefore, you want to make sure "00" does not occur, and three digit number should not exceed 255, as follows:

    if(t.length() > 3 || t.length() > 1 && t.charAt(0) == '0' || Integer.valueOf(t) > 255) {
        break;
    }
    

    I used a StringBuilder to build the solution, and it will require backtracking. By recording its length before recursive calls, int len = sb.length();, we can restore it back to len after recursion. if(i+1 != s.length()) means we are not at the last block, append a ".", and increment the dot count. Otherwise, helper(s, res, sb, i+1, count); will finish and record a solution.

    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if(s == null || s.length() == 0 || s.length() > 12) {
            return res;
        }
        helper(s, res, new StringBuilder(), 0, 0);
        return res;
    }
    
    private void helper(String s, List<String> res, StringBuilder sb, int pos, int count) {
        if(pos == s.length() && count == 3) {
            res.add(sb.toString());
            return;
        }
        if(count > 3) {  // count of dot more than 3, stop
            return;
        }
        for(int i = pos; i < s.length(); i++) {
            String t = s.substring(pos, i+1);
            if(t.length() > 3 || t.length() > 1 && t.charAt(0) == '0' || Integer.valueOf(t) > 255) {
                break;
            }
            int len = sb.length();
            
            sb.append(t);
            if(i+1 != s.length()) {
                sb.append(".");
                helper(s, res, sb, i+1, count+1);
            } else {
                helper(s, res, sb, i+1, count);
            }
            sb.setLength(len);
        }
    }

Log in to reply
 

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