LeetCode Solution, Easy, 282. Expression Add Operators

表達式加上運算符

題目敘述

Given a string `num` that contains only digits and an integer `target`, return all possibilities to add the binary operators `'+'`, `'-'`, or `'*'`between the digits of `num` so that the resultant expression evaluates to the `target` value.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

Example 5:

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

Constraints:

• `1 <= num.length <= 10`
• `num` consists of only digits.
• `-2^31 <= target <= 2^31 - 1`

Hint 1:

Note that a number can contain multiple digits.

Hint 2:

Since the question asks us to find all of the valid expressions, we need a way to iterate over all of them. (Hint: Recursion!)

Hint 3:

We can keep track of the expression string and evaluate it at the very end. But that would take a lot of time. Can we keep track of the expression's value as well so as to avoid the evaluation at the very end of recursion?

Hint 4:

Think carefully about the multiply operator. It has a higher precedence than the addition and subtraction operators. 1 + 2 = 3 1 + 2 - 4 --> 3 - 4 --> -1 1 + 2 - 4 12 --> -1 12 --> -12 (WRONG!) 1 + 2 - 4 12 --> -1 - (-4) + (-4 12) --> 3 + (-48) --> -45 (CORRECT!)

Hint 5:

We simply need to keep track of the last operand in our expression and reverse it's effect on the expression's value while considering the multiply operator.

解法解析

程式範例

Python
``````class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
N = len(num)

def recurse(index, prev_operand, current_operand, value, string):

# Done processing all the digits in num
if index == N:

# If the final value == target expected AND
# no operand is left unprocessed
if value == target and current_operand == 0:
return

# Extending the current operand by one digit
current_operand = current_operand*10 + int(num[index])
str_op = str(current_operand)

# To avoid cases where we have 1 + 05 or 1 * 05 since 05 won't be a
# valid operand. Hence this check
if current_operand > 0:

# NO OP recursion
recurse(index + 1, prev_operand,
current_operand, value, string)

recurse(index + 1, current_operand, 0,
value + current_operand, string + ['+', str_op])

# Can subtract or multiply only if there are some previous operands
if string:

# SUBTRACTION
recurse(index + 1, -current_operand, 0,
value - current_operand, string + ['-', str_op])

# MULTIPLICATION
recurse(index + 1, current_operand * prev_operand, 0, value -
prev_operand + (current_operand * prev_operand), string + ['*', str_op])
recurse(0, 0, 0, 0, [])
``````
JavaScript
``````/**
* @param {string} num
* @param {number} target
* @return {string[]}
*/
var addOperators = function (num, target) {
const result = [];

const backtrack = function (index, previous, current, path) {
if (index === num.length && current === target) {
result.push(path);
return;
}

for (let i = index; i < num.length; i++) {
if (i !== index && num[index] === '0') break;
const cur = parseInt(num.substring(index, i + 1));
if (index === 0) {
backtrack(i + 1, cur, cur, `\${path}\${cur}`);
} else {
backtrack(i + 1, cur, current + cur, `\${path}+\${cur}`);
backtrack(i + 1, -cur, current - cur, `\${path}-\${cur}`);
backtrack(
i + 1,
previous * cur,
current - previous + previous * cur,
`\${path}*\${cur}`
);
}
}
};

backtrack(0, 0, 0, '');
return result;
};
``````
Go
``````func addOperators(num string, target int) []string {
var ret = []string{}
var buf = make([]byte, len(num)*2) // shared bytes buffer

search(num, target, &ret, 0, 0, buf, 0)

return ret
}

// `l` is the length of valid content in `buf`
func search(num string, target int, ret *[]string, sum, diff int, buf []byte, l int) {
if len(num) == 0 {
if sum == target {
*ret = append(*ret, string(buf[0:l]))
}
return
}

var n = 0
// try all valid digit combinations
for i := 0; i < len(num); i++ {
n = n*10 + int(num[i]-'0')
var digits = num[0 : i+1]

if l == 0 {
copy(buf[l:], digits)
search(num[i+1:], target, ret, sum+n, n, buf, l+i+1)
} else {
copy(buf[l+1:], digits) // one copy for the three operators

buf[l] = '+'
search(num[i+1:], target, ret, sum+n, n, buf, l+1+i+1) // add `1 operator + (i+1) digits` to the length of buffer

buf[l] = '-'
search(num[i+1:], target, ret, sum-n, -n, buf, l+1+i+1)

buf[l] = '*'
search(num[i+1:], target, ret, sum-diff+diff*n, diff*n, buf, l+1+i+1)
}

if i == 0 && num[i] == '0' { // skip any number starts with 0
break
}
}
}
``````
Swift
``````class Solution {
func addOperators(_ num: String, _ target: Int) -> [String] {
var numArr = Array(num).map {Int(String(\$0))!}
var result = [String]()
helper(numArr, target, 0, 0, 0, "", &result)

return result
}

func helper(_ num: [Int],
_ target: Int,
_ index: Int,
_ eval: Int,
_ prevNum: Int,
_ path: String,
_ result: inout [String]) {
if target == eval && num.count == index {
result.append(path)
return
}

if index == num.count {
return
}

for i in index..<num.count {
if index != i && num[index] == 0 {
break
}

var val = 0
for j in index..<i+1 where j < num.count {
val *= 10
val += num[j]
}

if index == 0 {
helper(num, target, i+1, val, val, "\(val)", &result)
} else {
helper(num, target, i+1, eval+val, val, path+"+\(val)", &result)
helper(num, target, i+1, eval-val, -val, path+"-\(val)", &result)
helper(num, target, i+1, eval-prevNum+(val*prevNum), (val*prevNum), path+"*\(val)", &result)
}
}
}
}
``````
Kotlin
``````class Solution {
var digits = ""
var target: Long = 0

fun addOperators(num: String, target: Int): List<String> {
if (num.length == 0) emptyList<String>()

this.target = target.toLong()
this.digits = num
this.recurse(0, 0, 0, 0, mutableListOf<String>())
}

fun recurse(index: Int, prev: Long, cur: Long, value: Long, ops: MutableList<String>) {
val nums = this.digits
var prevOp = prev
var curOp = cur

// Done processing all the digits in num
if (index == nums.length) {

// If the final value == target expected AND
// no operand is left unprocessed
if (value == this.target && curOp == 0L) {
val sb = StringBuilder()
ops.subList(1, ops.size).forEach { v -> sb.append(v) }
}
return
}

// Extending the current operand by one digit
curOp = curOp * 10 + Character.getNumericValue(nums[index])
var rep = curOp.toString()
val length = nums.length

// To avoid cases where we have 1 + 05 or 1 * 05 since 05 won't be a
// valid operand. Hence this check
if (curOp > 0) {
// NO OP recursion
recurse(index + 1, prevOp, curOp, value, ops)
}

recurse(index + 1, curOp, 0, value + curOp, ops)
ops.removeAt(ops.size - 1)
ops.removeAt(ops.size - 1)

if (ops.size > 0) {
// SUBTRACTION
recurse(index + 1, -curOp, 0, value - curOp, ops)
ops.removeAt(ops.size - 1)
ops.removeAt(ops.size - 1)

// MULTIPLICATION