Backtracking solution in Java, easy to understand


  • 3
    T
    public class Solution {
        public List<String> restoreIpAddresses(String s) {
            List<String> result = new ArrayList<String>();
            if(s == null || s.length() == 0 || s.length() > 12){
                return result;
            }
            StringBuilder builder = new StringBuilder();
            helper(result, s, builder, 0, 0);
            return result;
        }
        
        private void helper(List<String> result, String s, StringBuilder builder, int start, int count){
            if(start == s.length() && count == 3){
                result.add(builder.toString());
                return;
            }
            for(int i = start + 1; i <= s.length(); i++){
                String tmp = s.substring(start, i);
                if(tmp.length() > 3 || tmp.length() > 1 && tmp.charAt(0) == '0' || Integer.parseInt(tmp) > 255){
                    return;
                }
                StringBuilder newBuilder = new StringBuilder(builder);
                if(newBuilder.length() != 0){
                    newBuilder.append(".");
                }
                newBuilder.append(tmp);
                helper(result, s, newBuilder, i, newBuilder.length() == tmp.length() ? count : count + 1);
            }
        }
    }

  • 3
    Y

    Like your answer, yet the part of using StringBuilder can be improved a bit. If you keep using the original StringBuilder object and trim its length after each recursion, it would save you some time. Some early termination will also help such as

    if(count > 3) {
        return;
    }
    

    My code as follows:

    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) {
            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.