class Solution {
public:
vector<string> addOperators(string num, int target) {
}
};
282. 给表达式添加运算符
给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加 二元 运算符（不是一元）+、- 或 * ，返回 所有 能够得到 target 的表达式。
注意，返回表达式中的操作数 不应该 包含前导零。
示例 1:
输入: num = "123", target = 6
输出: ["1+2+3", "1*2*3"]
解释: “1*2*3” 和 “1+2+3” 的值都是6。
示例 2:
输入: num = "232", target = 8
输出: ["2*3+2", "2+3*2"]
解释: “2*3+2” 和 “2+3*2” 的值都是8。
示例 3:
输入: num = "3456237490", target = 9191
输出: []
解释: 表达式 “3456237490” 无法得到 9191 。
提示：
1 <= num.length <= 10num 仅含数字-231 <= target <= 231 - 1原站题解
golang 解法, 执行用时: 8 ms, 内存消耗: 3.1 MB, 提交时间: 2023-09-14 15:27:49
func addOperators(num string, target int) (ans []string) {
n := len(num)
var backtrack func(expr []byte, i, res, mul int)
backtrack = func(expr []byte, i, res, mul int) {
if i == n {
if res == target {
ans = append(ans, string(expr))
}
return
}
signIndex := len(expr)
if i > 0 {
expr = append(expr, 0) // 占位，下面填充符号
}
// 枚举截取的数字长度（取多少位），注意数字可以是单个 0 但不能有前导零
for j, val := i, 0; j < n && (j == i || num[i] != '0'); j++ {
val = val*10 + int(num[j]-'0')
expr = append(expr, num[j])
if i == 0 { // 表达式开头不能添加符号
backtrack(expr, j+1, val, val)
} else { // 枚举符号
expr[signIndex] = '+'; backtrack(expr, j+1, res+val, val)
expr[signIndex] = '-'; backtrack(expr, j+1, res-val, -val)
expr[signIndex] = '*'; backtrack(expr, j+1, res-mul+mul*val, mul*val)
}
}
}
backtrack(make([]byte, 0, n*2-1), 0, 0, 0)
return
}
python3 解法, 执行用时: 628 ms, 内存消耗: 16.4 MB, 提交时间: 2023-09-14 15:27:17
class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
n = len(num)
ans = []
def backtrack(expr: List[str], i: int, res: int, mul: int):
if i == n:
if res == target:
ans.append(''.join(expr))
return
signIndex = len(expr)
if i > 0:
expr.append('') # 占位，下面填充符号
val = 0
for j in range(i, n): # 枚举截取的数字长度（取多少位）
if j > i and num[i] == '0': # 数字可以是单个 0 但不能有前导零
break
val = val * 10 + int(num[j])
expr.append(num[j])
if i == 0: # 表达式开头不能添加符号
backtrack(expr, j + 1, val, val)
else: # 枚举符号
expr[signIndex] = '+'; backtrack(expr, j + 1, res + val, val)
expr[signIndex] = '-'; backtrack(expr, j + 1, res - val, -val)
expr[signIndex] = '*'; backtrack(expr, j + 1, res - mul + mul * val, mul * val)
del expr[signIndex:]
backtrack([], 0, 0, 0)
return ans