Java AC solution, 19ms, beat 100.00%.


  • 33
    I

    I am surprised that it beats 100.00% other solutions, so i have to share this.

    void dfs(List<String> ret, char[] path, int len, long left, long cur, char[] digits, int pos, int target) {
        if (pos == digits.length) {
            if (left + cur == target) ret.add(new String(path, 0, len));
            return;
        }
        long n = 0;
        int j = len + 1;
        for (int i = pos; i < digits.length; i++) {
            n = n * 10 + digits[i] - '0';
            path[j++] = digits[i];
            path[len] = '+';
            dfs(ret, path, j, left + cur, n, digits, i + 1, target);
            path[len] = '-';
            dfs(ret, path, j, left + cur, -n, digits, i + 1, target);
            path[len] = '*';
            dfs(ret, path, j, left, cur * n, digits, i + 1, target);
            if (digits[pos] == '0') break; 
        }
    }
    public List<String> addOperators(String num, int target) {
        List<String> ret = new LinkedList<>();
        if (num.length() == 0) return ret;
        char[] path = new char[num.length() * 2 - 1];
        char[] digits = num.toCharArray();
        long n = 0;
        for (int i = 0; i < digits.length; i++) {
            n = n * 10 + digits[i] - '0';
            path[i] = digits[i];
            dfs(ret, path, i + 1, 0, n, digits, i + 1, target);
            if (n == 0) break;
        }
        return ret;
    }

  • 2
    O

    iambright, you are bright!

    I like your solution very much. Put left and cur for +- & * results respectively.

    I guess your avoidance of String/StringBuffer operation lets you outperform the previous solution 10x times.

    I am also wondering whether it can be accelerated more by adding memorization.

    My code learning from you, 18ms ^^:

    public class Solution {
        public List<String> addOperators(String num, int target) {
            char[] digit = num.toCharArray(), path = new char[num.length() * 2]; 
            List<String> ans = new ArrayList();
            long pureNum = 0;
            for (int i = 0; i < digit.length; i++) {
                pureNum = pureNum * 10 + (long)(digit[i] - '0');
                path[i] = digit[i];
                dfs(i + 1, i + 1, 0, pureNum, path, digit, target, ans);
                if (pureNum == 0) break; // not allow number with 0 prefix, except zero itself;
            }
            return ans;
        }
        
        private void dfs(int ip, int id, long toAdd, long toMult, char[] path, char[] digit, int target, List<String> ans) {
            if (id == digit.length && toAdd + toMult == target) {
                ans.add(String.valueOf(path, 0, ip));
                return;
            }
            long pureNum = 0;
            for (int i = 0; id + i < digit.length; i++) {
                pureNum = pureNum * 10 + (long)(digit[id + i] - '0');
                path[ip + i + 1] = digit[id + i];
                path[ip] = '+';
                dfs(ip + i + 2, id + i + 1, toAdd + toMult, pureNum, path, digit, target, ans);
                path[ip] = '-';
                dfs(ip + i + 2, id + i + 1, toAdd + toMult, -pureNum, path, digit, target, ans);
                path[ip] = '*';
                dfs(ip + i + 2, id + i + 1, toAdd, toMult * pureNum, path, digit, target, ans);
                if (pureNum == 0) break; // not allow number with 0 prefix, except zero itself;
            }
        }
    }

  • 1
    E

    Brilliant solution! I made a bit modification based on your version of code and shared it here:

    public List<String> addOperators(String num, int target) {
            List<String> ans = new ArrayList<String>();
            backtrack(num, 0, (long) target, 0, 0, ans, new char[2*num.length()], 0);
            return ans;
        }
        
        private void backtrack(String num, int idx, long tar, long val, long pre, List<String> ans, char[] res, int len) {
            if(idx == num.length() && tar == val)
                ans.add(new String(res, 0, len));
    
            int j = idx==0? len : len+1;
            long x = 0;
            for(int i = idx; i < num.length(); i++) {
                x = x*10 + (num.charAt(i) - '0');
                if(x < 10 && i-idx > 0) break;    // stop when leading zero found
                
                res[j++] = num.charAt(i);
                if(idx == 0){
                    backtrack(num, i+1, tar, val+x, x, ans, res, j);
                    continue;
                }
                res[len] = '+';
                backtrack(num, i+1, tar, val+x, x, ans, res, j);
                res[len] = '-';
                backtrack(num, i+1, tar, val-x, -x, ans, res, j);
                res[len] = '*';
                backtrack(num, i+1, tar, val-pre+pre*x, pre*x, ans, res, j);
            }
        }
    

  • 0
    H

    @edward5
    I think you got the same logic with the most votes method in the discussion, and both of the time complexity are O(4 ^ n), I am wondering that why your method has a much better runtime than the most votes.


  • 0
    E

    @hanyu92 I didn't see a big runtime difference between the two implementations, as they share the common logic.


  • 0
    Z

    @hanyu92 Editing a char array is way faster than editting with a StringBuilder or a String.


  • 0
    Y
    This post is deleted!

  • 0
    T

    @iaming
    char[] path = new char[num.length() * 2 - 1];

    Can you explain this line? thanks


  • 1
    X

    @tclu82 the number of digits is num.length(), so the largest possible number of operators is num.length() - 1. Therefore, a num.length() + num.length() - 1 = 2 * num.length() - 1 length of buffer is needed.


  • 0
    T

    @xtbbsnh got ya, thanks.


  • 1

    Make it easier understanding in helper function.

    class Solution {
        public List<String> addOperators(String num, int target) {
          int v = num.length();
          char[] sc = num.toCharArray();
          char[] path = new char[2 * v];
          List<String> res = new ArrayList();
          long n = 0;
          for(int i = 0; i < v; i++){
            n = n * 10 + (sc[i] - '0');
            path[i] = sc[i];
            helper(res, path, i + 1, sc, i + 1, 0, n, target);
            if(n == 0) break; // deal with '001' case, only `0` in the first loop will be handled.
          }
          return res;
        }
        
        /**
        path for store temporary result path, pathi is the end index
        sc is input char array, sci is end index
        left is what before we do the calculation
        cur is the new number from last recuisive call
        */
        void helper(List<String> res, char[] path, int pathi, char[] sc, int sci, long left, long cur, int target){
          if(sci == sc.length){
            if(left + cur == target){
               res.add(new String(path, 0, pathi));
            }
            return;
          }
          
          long n = 0;
          int signIndex = pathi;
          pathi++;//jump over signIndex
          for(int i = sci; i < sc.length; i++){
            //*put a new numberic char to path*  
            path[pathi] = sc[i];
            pathi++;
            //**************  
            n = n * 10 + (sc[i] - '0');//add a new digit
            path[signIndex] = '+';
            helper(res, path, pathi, sc, i + 1, left + cur, n, target);
            path[signIndex] = '-';
            helper(res, path, pathi, sc, i + 1, left + cur, -n, target);
            path[signIndex] = '*';
            helper(res, path, pathi, sc, i + 1, left, cur * n, target);
            if(n == 0) break; // deal with '001' case, only `0` in the first loop will be handled.
          }
        }
    }

Log in to reply
 

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