0%

[Leetcode]282. Expression Add Operators(C++)

题目描述

题目链接: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.

例子

例子 1

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

例子 2

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

例子 3

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

Constraints

  • 0 <= num.length <= 10
  • num only contain digits.

解题思路

这道题要用回溯的思路做,从字符串开头进行遍历,每遍历一个位置作为一个状态,从当前位置可以获得一个数字,接下里可以进行以下操作:

  • 从当前位置继续遍历字符串并将其后续字符也纳入到当前的数字中
  • 进行 + 操作,具体方法是将前一状态的结果加上当前数字,并递归调用本函数,传入更新后的路径以及路径结果,同时还需要将当前添加的新数字传入(这一步后面解释用法)
  • 进行 - 操作,具体方法同上类似,加法换成乘法即可,新添加的数字要传入当前的数字的相反数,表示是一个减操作
  • 进行 * 操作,这一步由于要考虑优先级,因此我们要先在前一状态结果中去除上一步操作(即前两部传入新添加的数字的作用),做法是 前一状态结果 - 新添加的元素,接下来进行: 更新后的前状态 + 新添加元素 * 当前数字,同样将 新添加元素 * 当前数字 作为当前操作数传入递归函数。

有几个地方需要注意下:

  • 凡是涉及到字符串转数字都需要考虑数字长度问题,在这道题目下字符串长度不超过 10,因此用 long 表示结果即可
  • 经过测试, 01 之类的数字不合法,因此在循环中需要考虑去除以 0 开头的数字情况
  • 在初识状态时(路径为空,或者索引是 0)不需要进行操作.

代码如下:

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <vector>
#include <string>

class Solution {
public:
std::vector<std::string> addOperators(std::string num, int target) {

m_target = target;
std::string path;
generatePath(num, 0, path, 0, 0);

return m_result;
}

private:
std::vector<std::string> m_result;
int m_target;

void generatePath(const std::string& num, int idx, std::string& path, long curr_eval, long prev_eval) {
if (idx == num.length()) {
if (curr_eval == m_target) {
m_result.push_back(path);
}
return;
}

long candidate = 0;
for (int i = idx; i < num.length(); ++i) {
if (i != idx && num[idx] == '0') break; // number begins with 0 and not 0 (e.g 01) is invalid

candidate *= 10;
candidate += (num[i] - '0');

std::string candidate_str = std::to_string(candidate);
if (idx == 0) {
// if this is the beginning of path, (e.g path == ""), no previous operator is required
path += candidate_str;
generatePath(num, i + 1, path, candidate, candidate);
path.erase(path.length() - candidate_str.length());
}
else {
// #1 : addition
path += "+";
path += candidate_str;
generatePath(num, i + 1, path, curr_eval + candidate, candidate);

// #2 : substraction
path[path.length() - candidate_str.length() - 1] = '-';
generatePath(num, i + 1, path, curr_eval - candidate, - candidate);

// #3 : multiplication
path[path.length() - candidate_str.length() - 1] = '*';
generatePath(num, i + 1, path, curr_eval - prev_eval + prev_eval * candidate, prev_eval * candidate);

// reset path by erase operator and new number
path.erase(path.length() - candidate_str.length() - 1);
}
}
}
};
  • 时间复杂度: O(2^n)
  • 空间复杂度: O(2^n)

GitHub 代码同步地址: 282.ExpressionAddOperators.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions