🌕🌕 282. 给表达式添加运算符

难度: 🌕🌕

问题描述

---

解法

class Solution {
    List<String> res = new ArrayList<>();
    String num;
    int len;
    int target;
    public List<String> addOperators(String num, int target) {
        // 思路：
        // 递归
        this.num = num;
        this.len = num.length();
        this.target = target;
        mySol(0, 0l, 0l, "");
        return res;
    }

    // preSum - 将 运算符 & prev 已经结合的结果
    // prev - 上一部分值，对于 +- 来说，相当于上一次的值，对于 * 来说，相当于 上一次的连乘结果
    private void mySol(int index, long preSum, long prev, String sb) {
        // 递归终止条件
        if(index == len) {
            if(preSum == target) {
                res.add(sb.toString());
            }
            return;
        }
        for(int i = index; i < len; i ++) {
            // 去除前导零
            if(num.charAt(index) == '0' && i > index) {
                break;
            }
            // 不含前导零 - [index, i]
            Long cur = Long.parseLong(num.substring(index, i + 1));
            // 判断是否是首个数字，即前面没有运算符
            if(index == 0) {
                mySol(i + 1, cur, cur, "" + cur);
            } else {
                // 尝试添加不同运算符
                mySol(i + 1, preSum + cur, cur, sb + "+" + cur); // +
                mySol(i + 1, preSum - cur, -cur, sb + "-" + cur); // -
                long realPreSum = preSum - prev; // 实际的运算结果，将最后一个连乘结果剔除
                long realCurSum = realPreSum + prev * cur; // 实际包含 cur 后的运算结果
                mySol(i + 1, realCurSum, cur * prev, sb + "*" + cur);
            }
        }
    }
}

---

输出