Expression Add Operators

https://leetcode.com/problems/expression-add-operators/description/

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Examples:

"123", 6 -> ["1+2+3", "1*2*3"]

"232", 8 -> ["2*3+2", "2+3*2"]

"105", 5 -> ["1*0+5","10-5"]

"00", 0 -> ["0+0", "0-0", "0*0"]

"3456237490", 9191 -> []

Thoughts

给一个由数字构成的字符串，往其中添加+-*/号使得最后eval等于target，返回所有可能的添加方法。all combination想dfs。 由于乘法具有最高优先级, 因此要把上个合理的乘法因子存下来。 而且根据题意中间数字如果是"06"应该跳过。

Code

class Solution {
public:
    void dfs(string &s, const int target, const int pos, const long cur, const long last, string path, vector<string> &res) {
        if (pos == s.size()) {
            if (cur == target) res.push_back(path);
            return;
        }

        for (int i = pos; i < s.size(); ++i) {
            if (pos != i && s[pos] == '0') break;
            const auto snum = s.substr(pos, i - pos + 1);
            const auto num = stol(snum);
            if (pos == 0) {
                dfs(s, target, i + 1, cur + num, num, snum, res);
                continue;
            }
            dfs(s, target, i + 1, cur + num, num, path + "+" + snum, res);
            dfs(s, target, i + 1, cur - num, -num, path + "-" + snum, res);
            dfs(s, target, i + 1, cur - last + last * num, last * num, path + "*" + snum, res);
        }
    }

    vector<string> addOperators(string num, int target) {
        vector<string> res;
        dfs(num, target, 0, 0, 0, "", res);
        return res;
    }
};

class Solution {
    private void helper(String num, int target, int pos, long cur, String str, List<String> res, long last) {
        if (pos == num.length()) {
            if (cur == target)
                res.add(str);
            return;
        }
        for (int i = pos; i < num.length(); i++) {
            if (i != pos && num.charAt(pos) == '0') {
                break; // To prevent '05'
            }
            long val = Long.parseLong(num.substring(pos, i + 1));
            if (pos == 0) {
                helper(num, target, i + 1, val, str + val, res, val);
            } else {
                helper(num, target, i + 1, cur + val, str + "+" + val, res, val);
                helper(num, target, i + 1, cur - val, str + "-" + val, res, -val);
                helper(num, target, i + 1, cur - last + last * val, str + "*" + val, res, last * val);
            }
        }
    }

    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<>();
        if (num.length() == 0) {
            return res;
        }
        helper(num, target, 0, 0, "", res, 0);
        return res;
    }
}

Thoughts

时间复杂度O(3 ^ N).