Beat 90% 3ms java backtracking


  • 0
    J

    leftP means the number of the left IP part, which is 1 to 4, and leftD means the left digit, hence if leftP3 < leftD, backtracking helper func should return directly. The code looks like redundant, anyone can show more concise code? Thx!*

        public List<String> restoreIpAddresses(String s) {
            int len = s.length();
            List<String> res = new ArrayList<>();
            if(len<4||len>12) return res;
            backtracking(s,new StringBuilder(), 4,s.length(),res);
            return res;
        }
        
        private void backtracking(String orig, StringBuilder cur, int leftP, int leftD, List<String> res){
            if(leftP==0&&leftD==0){
                res.add(cur.substring(0,cur.length()-1));
                return;
            }
            if(leftP*3<leftD) return;
            for(int i =1; i <= Math.min(leftD,3) ; i++){
                String temp = orig.substring(orig.length()-leftD,orig.length()-leftD+i);
                if(!checkValid(temp)) continue;
                cur.append(temp);
                cur.append(".");
                backtracking(orig,cur,leftP-1,leftD-i,res);
                cur.delete(cur.length()-1-i,cur.length());
            }
        }
        
        private boolean checkValid(String s){
            if(s.length()>1&&s.charAt(0)=='0') return false;
            int i = Integer.parseInt(s);
            return i >=0 && i <= 255;
        }
    }

Log in to reply
 

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