Java easy to read backtracking solution


  • 1
    Y

    Java backtracking solution. Idea is to get a number from 1 digit to 3 digit and backtracking. I used a StringBuilder to keep track of the string therefore need another variable k to keep track of the segments that have been built so far. Anytime when k <= 0, we can break the for loop for further recursion. if(t.charAt(0) == '0' && t.length() > 1) is used to make sure we don't get multiple zeroes in one segment of IP.

    public class Solution {
        public List<String> restoreIpAddresses(String s) {
            List<String> res = new ArrayList<>();
            
            helper(res, s, new StringBuilder(), 0, 4);
            return res;
        }
    
    private void helper(List<String> res, String s, StringBuilder sb, int pos, int k) {
        if(pos == s.length()) {
            if(k == 0) {
                res.add(sb.toString());
            }
            return;
        }
        for(int i = pos; i < s.length() && i < pos + 3; i++) {
            if(k <= 0) {
                break;
            }
            String t = s.substring(pos, i + 1);
            if(t.charAt(0) == '0' && t.length() > 1) {
                break;
            }
            if(Integer.valueOf(t) < 256) {
                int len = sb.length();
                sb.append(t);
                if(i != s.length() - 1) {
                    sb.append(".");
                }
                helper(res, s, sb, i+1, k-1);
                sb.setLength(len);
            }
        }
    }
    

    }


Log in to reply
 

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