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;
};

參考資料