Easy Java code of backtracking within 16 lines


  • 23
    W
        public List<String> restoreIpAddresses(String s) {
            List<String> res = new ArrayList<>();
            helper(s,"",res,0);
            return res;
        }
        public void helper(String s, String tmp, List<String> res,int n){
            if(n==4){
                if(s.length()==0) res.add(tmp.substring(0,tmp.length()-1));
                //substring here to get rid of last '.'
                return;
            }
            for(int k=1;k<=3;k++){
                if(s.length()<k) continue;
                int val = Integer.parseInt(s.substring(0,k));
                if(val>255 || k!=String.valueOf(val).length()) continue;
                /*in the case 010 the parseInt will return len=2 where val=10, but k=3, skip this.*/
                helper(s.substring(k),tmp+s.substring(0,k)+".",res,n+1);
            }
        }

  • 3
    T

    I think in the for loop, the first "continue" can be replaced by "break". And at the beginning of the helper function, we can add one conditional branch to save some time. Here it is : if (s.length() > 3 * (4 - n)) return;


  • 0
    A

    what is the complexity of the above solution and how would you calculate it?


Log in to reply
 

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