Java AC solution, 19ms, beat 100.00%.


  • 32
    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.


Log in to reply
 

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