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

  • 0

    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){
        else if (qIndex==4 ){
            if (index > cs.length-1){
                StringBuilder bldr = new StringBuilder();
                for (int i=0; i<4; i++){
                result.add(bldr.substring(0, bldr.length()-1));
        for (int len =0; len <3 && index+len<cs.length; len++){
            int num = getNum(cs, index, index+len);
            if (num<0 || num>255){
            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++){
        return result;

Log in to reply

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