每日leetcode-282

282 给表达式添加运算符

给定一个仅包含数字 0-9 的字符串和一个目标值，在数字之间添加二元运算符（不是一元）+、- 或 * ，返回所有能够得到目标值的表达式。

示例 1:

输入: num = “123”, target = 6
输出: [“1+2+3”, “123”]
示例 2:

输入: num = “232”, target = 8
输出: [“23+2”, “2+32”]
示例 3:

输入: num = “105”, target = 5
输出: [“1*0+5”,”10-5”]
示例 4:

输入: num = “00”, target = 0
输出: [“0+0”, “0-0”, “0*0”]
示例 5:

输入: num = “3456237490”, target = 9191
输出: []

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/expression-add-operators
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

尝试

做了一个特别naive的做法，直接简单递归与求值。

class Solution {
public:
    bool checkAns(const string &data, int target) {
        stack<char> op;
        stack<long long> num;
        int len = data.size();
        long long now_number = 0;
        for (int i = 0; i < len; i++) {
            if (data[i] >= '0' && data[i] <= '9') {
                now_number = now_number * 10 + data[i] - '0';
                continue;
            }
            num.push(now_number);
            now_number = 0;
            if (data[i] == '+' || data[i] =='-' || data[i] == '#') {
                // Calculate all before
                while (!op.empty()) {
                    char c = op.top();
                    op.pop();
                    long long b = num.top();
                    num.pop();
                    long long a = num.top();
                    num.pop();
                    if (c == '*') {
                        num.push(a * b);
                    }
                    else if (c == '+') {
                        num.push(a + b);
                    }
                    else {
                        num.push(a - b);
                    }
                }
                op.push(data[i]);
            }
            else if (data[i] == '*') {
                char c = op.empty() ? ' ' : op.top();
                if (c == '*') {
                    op.pop();
                    long long b = num.top();
                    num.pop();
                    long long a = num.top();
                    num.pop();
                    num.push(a * b);
                    op.push('*');
                }
                else {
                    op.push('*');
                }
            }
        }
        return num.top() == target;
    }

    void getResult(const string &already, const string &todo, int target, vector<string> &ans) {
        if (todo.empty()) {
            if (checkAns(already + "#", target)) {
                ans.push_back(already);
            }
        }
        else {
            if (*(already.cend() - 1) != '0') {
                getResult(already + todo.substr(0, 1), todo.substr(1, todo.size() - 1), target, ans);
            }
            getResult(already + "+" + todo.substr(0, 1), todo.substr(1, todo.size() - 1), target, ans);
            getResult(already + "-" + todo.substr(0, 1), todo.substr(1, todo.size() - 1), target, ans);
            getResult(already + "*" + todo.substr(0, 1), todo.substr(1, todo.size() - 1), target, ans);
        }
    }

    vector<string> addOperators(string num, int target) {
        vector<string> ans;
        getResult(num.substr(0, 1), num.substr(1, num.size() - 1), target, ans);
        return ans;
    }
};

很明显会超时。

解答

在 https://www.jianshu.com/p/22c9115b3a27 看到的。

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        addOperatorsDFS(num, target, 0, 0, "", res);
        return res;
    }
    void addOperatorsDFS(string num, int target, long long diff, long long curNum, string out, vector<string> &res) {
        if (num.size() == 0 && curNum == target) { // 当前已经处理完了所有的
            res.push_back(out);
        }
        for (int i = 1; i <= num.size(); ++i) {
            string cur = num.substr(0, i);
            if (cur.size() > 1 && cur[0] == '0') return;  // 如果当前的数字以0开头并且不是0，就说明操作符肯定只能在0后面，不能继续向后看切割位置
            string next = num.substr(i);  // 在i的地方切成了两部分，cur和next
            if (out.size() > 0) { // 之前已经计算过了有了一个数字的结果之后
                addOperatorsDFS(next, target, stoll(cur), curNum + stoll(cur), out + "+" + cur, res);  // +，当前的diff是cur对应的数字，计算完成的结果是curNum + stoll(cur)，已经计算完成的部分的字符串是out + "+" + cur
                addOperatorsDFS(next, target, -stoll(cur), curNum - stoll(cur), out + "-" + cur, res);  // -，直接把-当作是+负数，这样操作没有什么问题
                addOperatorsDFS(next, target, diff * stoll(cur), (curNum - diff) + diff * stoll(cur), out + "*" + cur, res);  // *，这里需要把前面的一个的结果（diff）拿出来，这样新的diff就是diff * stoll(cur)，因为把diff去掉了所以前面的剩下的结果是 (curNum - diff) ，总的结果就是(curNum - diff) + diff * stoll(cur)
            } else {
                addOperatorsDFS(next, target, stoll(cur), stoll(cur), cur, res);  // 这时还没有开始计算，所以需要把最开始的第一个数字搞出来
            }
        }
    }
};

long long diff, long long curNum, string out这三个参数分别是指上一次加上的计算结果，当前的计算结果，产生的已经计算过的字符串。

这里是把减法看成了加上负数，所以总的来说只是在处理乘法和加法的关系。

在后面写上乘号之后，需要把乘号前面的部分搞出来，所以就是需要diff的地方。

这样的做法可以很好地避免重复计算的过程，我之前的做法就会导致同样的一部分字符串计算求值算很多遍。