Java easy understand backtrack code


  • 0
    F
    public class Solution {
        public List<String> restoreIpAddresses(String s) {
            List<String> ans = new ArrayList<>();
            if (s == null || s.length() == 0) return ans;
            backtrack(ans, s, new ArrayList<String>(), 0);
            return ans;
        }
        public boolean isValid(String s) {
            if (s.length() > 3 || s.length() == 0 || (s.charAt(0) == '0' && s.length() > 1) || Integer.valueOf(s) > 255) return false;
            return true;
        }
        public void backtrack(List<String> ans, String s, List<String> tmp, int start) {
            if (start == s.length() && tmp.size() == 4) {
                String strs = tmp.get(0);
                for (int i = 1; i < tmp.size(); i++) strs = strs + "." + tmp.get(i);
                ans.add(strs);
            }
            else if (tmp.size() > 4) return;
            else {
                for (int i = 1; i < 4 && start + i <= s.length(); i++) {
                    if (!isValid(s.substring(start, start + i))) continue;
                    tmp.add(s.substring(start, start + i));
                    backtrack(ans, s, tmp, start + i);
                    tmp.remove(tmp.size() - 1);
                }
            }
        }
    }
    

Log in to reply
 

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