241. Different Ways to Add Parentheses

Leetcode 问题: 241. Different Ways to Add Parentheses
Categories:
Tags:

题目

Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.

给予一个字串，裡面包含数字及运算符号，回传将数字及运算符号用括号群组后，所有可能的计算答案阵列

Example

Input: expression = "2-1-1"
Output: [0,2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2

Input: expression = "2*3-4*5"
Output: [-34,-14,-10,-10,10]
Explanation:
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

演算法

1. 将传入的字串依照运算符号分群

每个部分的答案可以透过运算符号分群切割，个别取得双边的答案阵列，所以 2*3-4*5 可以变成

运算符号 运算符号左方 运算符号右方
* 2 3-4*5
- 2*3 4*5
* 2*3-4 5

然后分别取得左右方运算结果，而像是 3-4*5 可以变成

运算符号 运算符号左方 运算符号右方
- 3 4*5
* 3-4 5

然后再分别取得左右方运算结果，而像是 4*5 可以变成

运算符号 运算符号左方 运算符号右方
* 4 5

最后的数字 4 与 5 就会变成，无法再透过运算符号分割的数字，就会直接变成答案回传

回传后并透过运算符号计算，可以获得答案是 20

运算符号 运算符号左方 运算符号右方 运算答案
* 4 5 4*5 = 20

然后上方的 3-4 透过同样逻辑运算，会得到 -1

运算符号 运算符号左方 运算符号右方 运算答案
- 3 4 3-4 = -1

最后上方的 3-4*5 答案就会变成

然后分别取得左右方运算结果，而像是 3-4*5 得答案可以获得可能是 -17 或是 -5

运算符号 运算符号左方 运算符号右方 运算答案
- 3 4*5 3-20 = -17
* 3-4 5 -1 * 5 = -5

2. 计算运算符号左右结果排列组合答案

而第一部分的答案依照 3-4*5 取得的可能答案是 [-17, -5] 运算后可能的答案会变成 [-34, -10]

运算符号 运算符号左方 运算符号右方 运算答案
* 2 3-4*5 2*(-17) = -34 或 2*(-5) = -10

这样所有的切割排列组合，获得的答案会是

运算符号 运算符号左方 运算符号右方 运算答案
* 2 3-4*5 [-34, -10]
- 2*3 4*5 [-14]
* 2*3-4 5 [-10, 10]

最后就可以得到所有可能的运算答案是 [-34,-14,-10,-10,10]

3. 纪录运算结果快取

将运算的结果记录下当，当下次有相同运算结果，直接回传已运算的结果

答案

JavaScript

// 运算结果 Cache
var computeCache = {};
function diffWaysToCompute(expressionText) {
    if (computeCache[expressionText]) {
        // 假如有之前运算的结果，直接回传运算结果
        return computeCache[expressionText];
    }
    // 最后结果清单
    var computeAnswerList = [];
    // 解析字串
    for (var i = 0; i < expressionText.length; i++) {
        // 目前取得的字串
        var currentLetter = expressionText[i];
        if (currentLetter == '-' || currentLetter == '+' || currentLetter == '*') {
            // 如果是运算符号的话
            // 排除运算符号，取左方运算数字
            var leftPartitionExpressionText = expressionText.slice(0, i);
            // 排除运算符号，取右方运算数字
            var rightPartitionExpressionText = expressionText.slice(i + 1);
            // 运算左右部分结果
            var leftComputeResult = diffWaysToCompute(leftPartitionExpressionText);
            var rightComputeResult = diffWaysToCompute(rightPartitionExpressionText);
            // 计算左右两方运算结果排列组合
            for (var leftIndex = 0; leftIndex < leftComputeResult.length; leftIndex++) {
                // 左方数字结果
                var leftValue = Number(leftComputeResult[leftIndex]);
                for (var rightIndex = 0; rightIndex < rightComputeResult.length; rightIndex++) {
                    // 右方数字结果
                    var rightValue = Number(rightComputeResult[rightIndex]);
                    var finalComputeResult = void 0;
                    // 根据运算符号取得最后运算结果
                    switch (currentLetter) {
                        case '+':
                            finalComputeResult = leftValue + rightValue;
                            break;
                        case '-':
                            finalComputeResult = leftValue - rightValue;
                            break;
                        case '*':
                            finalComputeResult = leftValue * rightValue;
                            break;
                    }
                    // 将运算结果加入清单
                    computeAnswerList.push(finalComputeResult);
                }
            }
        }
    }
    if (computeAnswerList.length == 0) {
        // 假如没有储存任何答案清单，表示这个是个数字，直接将数字储存到阵列中
        computeAnswerList.push(Number(expressionText));
    }
    // 纪录快取
    computeCache[expressionText] = computeAnswerList;
    return computeAnswerList;
}

TypeScript

// 运算结果 Cache
let computeCache:any = {};
function diffWaysToCompute(expressionText: string): number[] {
    if (computeCache[expressionText]) {
        // 假如有之前运算的结果，直接回传运算结果
        return computeCache[expressionText];
    }

    // 最后结果清单
    let computeAnswerList: number[] = [];
    // 解析字串
    for (let i = 0; i < expressionText.length; i++) {
        // 目前取得的字串
        let currentLetter = expressionText[i];
        if (currentLetter == '-' || currentLetter == '+' || currentLetter == '*') {
            // 如果是运算符号的话
            // 排除运算符号，取左方运算数字
            let leftPartitionExpressionText = expressionText.slice(0, i);
            // 排除运算符号，取右方运算数字
            let rightPartitionExpressionText = expressionText.slice(i + 1);
            // 运算左右部分结果
            let leftComputeResult = diffWaysToCompute(leftPartitionExpressionText);
            let rightComputeResult = diffWaysToCompute(rightPartitionExpressionText);

            // 计算左右两方运算结果排列组合
            for (let leftIndex = 0; leftIndex < leftComputeResult.length; leftIndex++) {
                // 左方数字结果
                let leftValue: number = Number(leftComputeResult[leftIndex]);
                for (let rightIndex = 0; rightIndex < rightComputeResult.length; rightIndex++) {
                    // 右方数字结果
                    let rightValue: number = Number(rightComputeResult[rightIndex]);
                    let finalComputeResult;
                    // 根据运算符号取得最后运算结果
                    switch (currentLetter) {
                        case '+':
                            finalComputeResult = leftValue + rightValue;
                            break;
                        case '-':
                            finalComputeResult = leftValue - rightValue;
                            break;
                        case '*':
                            finalComputeResult = leftValue * rightValue;
                            break;
                    }

                    // 将运算结果加入清单
                    computeAnswerList.push(finalComputeResult);
                }
            }
        }
    }

    if (computeAnswerList.length == 0) {
        // 假如没有储存任何答案清单，表示这个是个数字，直接将数字储存到阵列中
        computeAnswerList.push(Number(expressionText));
    }

    // 纪录快取
    computeCache[expressionText] = computeAnswerList;
    return computeAnswerList;
};

参考资料