LeetCode: 282. Expression Add Operators

发表于 | 分类于

题目描述

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.

Example 1:

1
2
Input: num = "123", target = 6
Output: ["1+2+3", "1*2*3"]

Example 2:

1
2
Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]

Example 3:

1
2
Input: num = "105", target = 5
Output: ["1*0+5","10-5"]

Example 4:

1
2
Input: num = "00", target = 0
Output: ["0+0", "0-0", "0*0"]

Example 5:

1
2
Input: num = "3456237490", target = 9191
Output: []

hard题

这题考的还是对recursion够不够熟悉，如果够熟悉的话实现起来很简单，也不会有什么bug。

我们需要定义一个进行recursion的函数tmpOperators，该函数的输入有五个，分别是当前剩下的字符串num，目标target，当前的计算值tmpSum（这里命名有点问题…），以及保留当前加减法的当前值（因为乘法的优先级比较高，需要保留一个值来实现乘法先计算的特点），以及当前函数的运算符号和值。

在每个tmpOperators中，需要对num进行切割，对每种切割方法，都是用’+’, ‘-‘, ‘*‘去拼接结果。我们令切割后的前面一部分为当前需要计算的值curInt，余下的叫res。对于加法，下一次需要传入的tmpSum = tmpSum + curInt， tmpAdd = curInt，减法与加法相似。然而对于乘法，下一次的tmpSum必须要先减去tmpAdd后再乘以tmpAdd*curInt，相当于减去最后一次加法（减法）后，乘上这个值乘以当前curInt的值（细细体会一下，是这样的）。

不过这题的坑有两个

  • 首先字符串可能会很长，所以字符串转int需要转成long long
  • 对于开头为0的字符串，这个0是必须要切割下来的，比如说对于”05”，必须要”0+5”或”0-5”或”0*5”，而不能保留”05”

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
private:
    vector<string> _result;
    void tmpOperators(string num, int target, long long int tmpSum, long long int tmpAdd, string operators) {
        if (num == "" && tmpSum == target)
            _result.push_back(operators);

        for (int i = 1; i <= num.length(); i++) {
            string cur = num.substr(0, i);
            string res = num.substr(i);
            long long int curInt = stoll(cur);

            //+
            tmpOperators(res, target, tmpSum + curInt, curInt, operators + '+' + cur);

            //-
            tmpOperators(res, target, tmpSum - curInt, -curInt, operators + '-' + cur);

            //*
            tmpOperators(res, target, tmpSum - tmpAdd + tmpAdd * curInt, tmpAdd * curInt, operators + '*' + cur);

            if (num[0] == '0')
                break;
        }
        
        return;
    }
public:
    vector<string> addOperators(string num, int target) {
        for (int i = 1; i <= num.length(); i++) {
            tmpOperators(num.substr(i), target, stoll(num.substr(0, i)), stoll(num.substr(0, i)), num.substr(0, i));

            if (num[0] == '0')
                break;
        }
        return _result;
    }
};