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.

題目翻譯

題目會給兩個參數，一個是字串 num，這個字串中都只包含數字。另一個參數是 target。然後想要找出在字串 num 中所有數字之間，可以插入 +, - 或 * 的 operator。最後可以等於 target 的所有組合。

解法解析

這題的解法主要就是會使用到遞迴的方式，一層一層的去找出各種可能的答案。先以 python 的範例來說。在每次的遞迴時，先去判斷 index 是不是到最後了，如果是再來判斷總合是否與 target 相等，並且沒有剩下要執行的 operator，就會是要回傳的組合，儲存在 answers 裡面。在每次的遞迴裡面去分別計算如果插入 operator -, + 或 * 的各種情境。

程式範例

Python

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

        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:
                    answers.append("".join(string[1:]))
                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)

            # ADDITION
            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, [])
        return answers

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 answer = mutableListOf<String>()
    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>())
        return this.answer
    }

    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) }
                this.answer.add(sb.toString())
            }
            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)
        }

        // ADDITION
        ops.add("+")
        ops.add(rep)
        recurse(index + 1, curOp, 0, value + curOp, ops)
        ops.removeAt(ops.size - 1)
        ops.removeAt(ops.size - 1)

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

            // MULTIPLICATION
            ops.add("*")
            ops.add(rep)
            recurse(index + 1, curOp * prevOp, 0, value - prevOp + (curOp * prevOp), ops)
            ops.removeAt(ops.size - 1)
            ops.removeAt(ops.size - 1)
        }
    }
}