typical backtracking problem


  • 0
    B

    it's just another typical backtracking problem.
    Share my code below. Hope it helps

    public class Solution {
        public List<String> restoreIpAddresses(String s){
            List<String> ans = new ArrayList<>();
            helper(ans, 0, 0, s, new ArrayList<>());
            return ans;
        }
        private void helper(List<String> ans, int level, int start, String input, List<String> cur){
            if (start >= input.length()){
                return;
            }
            if (level == 3){
                if (input.length() - start > 3){
                    return;
                }
                String candidate = input.substring(start, input.length());
                if (isValid(candidate)){
                    cur.add(candidate);
                    ans.add(getAns(cur));
                    cur.remove(cur.size() - 1);
                }
                return;
            }
            for (int i = 1 ; i <= 3 ; i++){
                int end = start + i;
                end = Math.min(end, input.length());
                String candidate = input.substring(start, end);
                if (isValid(candidate)){
                    cur.add(candidate);
                    helper(ans, level + 1, end, input, cur);
                    cur.remove(cur.size() - 1);
                }
            }
        }
        private boolean isValid(String s){
            if (s.startsWith("0") && s.length() > 1){
                return false;
            }
            int value = Integer.valueOf(s);
            return value <= 255;
        }
        private String getAns(List<String> cur){
            StringBuilder sb = new StringBuilder();
            for (int i = 0 ; i < cur.size() ; i++){
                sb.append(cur.get(i));
                if (i != cur.size() - 1){
                    sb.append(".");
                }
            }
            return sb.toString();
        }
    }
    

Log in to reply
 

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