Share my Java backtracking sol beating 96%


  • 0
    L

    Note: Specially dealing with 0 at start of a period.

    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<String>();
        backtracking(s,"",0,0,0,result);
        return result;
    }
    
    //注意:对每段中0在首位的要处理 比如input "010010"中010.是不允许的
    private void backtracking(String s,String curStr,int curNum,int start,int dotCnt,List<String> result){
        if(dotCnt > 3){
            return;
        }
    
        if(start == s.length()){
            if(dotCnt == 3 && curStr.charAt(curStr.length()-1) != '.') {
                result.add(curStr);
            }
            return;
        }
    
        // Add dot now
        if(!curStr.isEmpty() && curStr.charAt(curStr.length()-1) != '.'){
            backtracking(s,curStr+'.',0,start,dotCnt+1,result);
        }
    
        //(但0在本段有>=2个digit时不可在首位的特殊处理
        if(curNum == 0 && s.charAt(start) == '0'){
            if(start < s.length()-1) backtracking(s,curStr+"0.",0,start+1,dotCnt+1,result);
            //对最后一位是0的特殊处理,不然出现最后0.
            else backtracking(s,curStr+"0",0,start+1,dotCnt,result);
            return;
        }
    
        // Not add dot now
        int temp = curNum*10+(s.charAt(start)-'0');
        if(temp <= 255){
            backtracking(s,curStr+s.charAt(start),temp,start+1,dotCnt,result);
        }
    }

Log in to reply
 

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