Java easy backtracking solution


  • 0
    K
    public class Solution {
        public List<String> restoreIpAddresses(String s) {
            List<String> result = new ArrayList<String>();        
            if(s.length() <4 || s.length() > 12) return result;
            dfs(result, "", s, 0);
            return result;
        }
        
        public void dfs(List<String> result, String path, String s, int start) {
            if(start == s.length() && path.length() == s.length()+3) {
                result.add(path);
                return;
            }
            for(int i = start+1; i <= s.length() && i <= start+3; ++i) {
                String temp = s.substring(start, i);
                if(isValid(temp)) {
                    dfs(result, (path.length() == 0 ? "" : path+".")+temp, s, i);
                }
            }
        }
        
        public boolean isValid(String temp) {
            if(temp.charAt(0) == '0') return temp.length() == 1;
            int num = Integer.valueOf(temp);
            return num >=0 && num <= 255;
        }
    }
    

  • 0
    M

    @katherine342
    I use similar solution as yours, but can not figure out the time complexity. Could you explain it? Thx


Log in to reply
 

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