LeetCode：282. Expression Add Operators

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:

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: []

解题思路 —— 递归求解

递归列举出所有出符合要求的表达式，需要注意的是表达式的每个数字不能有前置零

AC 代码

func mulOperators(num string) map[string] int{
    ans := make(map[string] int)
    
    for i := 1; i < len(num); i++{
        // 前置 0 无效
        if i != 1 && num[0] == '0' {
            break
        }
        
        for str, prod := range mulOperators(num[i:]){
            rhv, _ := strconv.Atoi(num[0:i])
            ans[num[0:i]+"*"+str] = prod * rhv
        }
    }
    
    // 前置 0 无效
    if len(num) == 1 || num[0] != '0' {
        ans[num], _ = strconv.Atoi(num)
    }
    
    return ans
}

func addOperators(num string, target int) []string {
    var ans []string
    
    for i := 0; i < len(num); i++{
        // mulOperators 罗列出后续出现的项可能的组合
        for rhv, prod := range mulOperators(num[i:len(num)]){
            if prod == target && i == 0{
                ans = append(ans, rhv)
            } else if i != 0 {
                // target = lhv - rhv 的情况
                for _, lhv := range addOperators(num[0:i], prod+target) {
                    ans = append(ans, lhv + "-" + rhv)
                }
                
                // target = lhv + rhv 的情况
                for _, lhv := range addOperators(num[0:i], target-prod) {
                    ans = append(ans, lhv + "+" + rhv)
                }
            }
        }
    }
    
    return ans
}