Data structure matters: share my 2 ms backtracking Java that beats 97.7% java submission


  • 0
    L

    Using a simple array instead of a Deque or LinkedList to store the numbers really makes huge difference. Once I changed, my submission beat 97.7% submissions while the one use LinkedList is around 31.x%. Here is the code.

    public List<String> restoreIpAddresses(String s) {
        List<String> res = new LinkedList<>();
        if (s==null || s.length()==0){
            return new ArrayList<String>();
        }
        int[] dq = new int[4];
        restore(s.toCharArray(), 0, dq, 0, res);
        return res;
    }
    
    
    private void restore(char [] cs, int index, int[] dq, int qIndex, List<String> result ){
        if (qIndex == 3 && cs.length-index>3){
            return;
        }
        else if (qIndex==4 ){
            if (index > cs.length-1){
                StringBuilder bldr = new StringBuilder();
                for (int i=0; i<4; i++){
                    bldr.append(dq[i]).append(".");
                }
                result.add(bldr.substring(0, bldr.length()-1));
    
            }
            return;
        }
    
        for (int len =0; len <3 && index+len<cs.length; len++){
            int num = getNum(cs, index, index+len);
            if (num<0 || num>255){
                continue;
            }
            dq[qIndex]=num;
            restore(cs, index+len+1, dq, qIndex+1, result);
    
        }
    
    }
    private int getNum(char[] cs, int s, int e){
        int result = 0;
        
        if (cs[s] == '0' && e-s>0){
            return -1;
        }
        
        for (int i=s; i<=e; i++){
            result=result*10+(cs[i]-'0');
        }
        return result;
    }

Log in to reply
 

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