LeetCode 241. Different Ways to Add Parentheses

 关注
发布于: 2020 年 05 月 24 日
LeetCode 241. Different Ways to Add Parentheses
@(LeetCode)
﻿
问题描述﻿
给定一个由数字和运算符组成的字符串，返回数字与运算符所有可能的组合方式的计算结果。有效的操作符为 +，- 和 *。
﻿
栗 1：
输入："2-1-1"
输出：[0, 2]
﻿
可能的组合方式如下：
﻿
((2-1)-1) = 0 
(2-(1-1)) = 2
﻿
栗 2：
输入："2*3-4*5"
输出：[-34, -14, -10, -10, 10]
﻿
可能的组合方式如下：
﻿
(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
﻿
想看英文原文的戳这里。
﻿
解题思路﻿
这里的题意是忽略运算符优先级，找出所有可能的数字与运算符的结合方式，再计算其结果。
﻿
栗子分析﻿
我的思路是由分析栗 2 得出的，让我们再来整理一下栗 2 的结果。
﻿
表达式为："2*3-4*5"。
﻿
所有可能的组合方式如下，我稍微整理了下。
// 第一组组合。由第一个操作符 '*' 连接左右两边的组合
2*(3-(4*5)) = -34
2*((3-4)*5) = -10
﻿
// 第二组组合。由第二个操作符 '-' 连接左右两边的组合
(2*3)-(4*5) = -14
﻿
// 第三组组合。由第三个操作符 '*' 连接左右两边的组合
(2*(3-4))*5 = -10
((2*3)-4)*5 = 10
﻿
从上，我们可以发现一些规律。
﻿
第一组组合由  '*' 分隔表达式；第二组组合由 '-' 分隔；第三组组合由 '*' 分隔，且从整体上来看将表达式分成了左右两部分。再细看左右两部分，不难发现：
﻿
如果左/右两部分是表达式，则继续按照上述方式进行分解组合。
如果左/右两部分是数字，则不再分解。
﻿
比如：2*(3-4*5)，其右边部分 (3-4*5) 是个表达式，又可分解组合如下：
3-(4*5)
(3-4)*5
而左边 2 是数字，不可再分解。因此，2*(3-4*5) 所有的组合方式为：
2*(3-(4*5))
2*((3-4)*5)
﻿
再来看个复杂些的栗子。
﻿
比如某个表达式为：(2-1*3)*(3-4*5)，中间的 '*' 将表达式分为 (2-1*3) 与 (3-4*5)。
﻿
其中左边表达式 (2-1*3) 的组合方式如下：
2-(1*3) = -1
(2-1)*3 = 3
﻿
右边表达式 (3-4*5) 的组合方式如下：
3-(4*5) = -17
(3-4)*5 = -5
﻿
那么该表达式的所有组合方式有 2 * 2 = 4 种，为左右组合方式的两两组合。如下所示：
(2-(1*3))*(3-(4*5)) = -1 * -17 = 17
((2-1)*3)*(3-(4*5)) = 3 * -17 = -51
﻿
(2-(1*3))*((3-4)*5) = -1 * -5 = 5
((2-1)*3)*((3-4)*5) = 3 * -5 = -15
﻿
因此，以上的结论可表述为：表达式的组合方式 =「左边表达式可能的组合」* 「右边表达式可能的组合」，即再次两两组合。
﻿
弄清楚如何进行组合，那么下一步就是计算组合的运算结果。
﻿
何时能计算结果？当分解到左右两边都为数字时，这时候就需要计算结果了。根据中间操作符，左右两边的数字即可运算得出。但是要注意一点，由于组合方式有多种，那么组合计算的结果也有多个，需要用数组保存。
﻿
对于上述栗子 (2-1*3)*(3-4*5)，其所有组合的值为：
// 两个数组元素两两相乘
[-1, 3] * [-17, -5] = [17, 5, -51, -15]
﻿
所以，我们也能得出如下结论：表达式所有组合的值 = 「左边表达式组合的值」op「右边表达式组合的值」。其中 op 代表操作符。
﻿
思路总结﻿
根据以上栗子的讲解，我们总结一下思路：
首先将整个表达式看成只有两部分组成，由一个操作符隔开。
遍历表达式中所有的操作符，根据不同位置的操作符将其划分为两部分。
选定一个操作符，该操作符会将表达式分为左右两部分。如果左/右部分也是一个表达式，则继续按上述方式分解。最终的组合为左右两部分结果的再次两两组合。
由于子表达式会有多个组合，所以需要用数组保存所有组合方式运算后的值。为了一致性处理，即使只是单个值，也要以数组形式返回。
表达式所有组合的值为「左表达式所有组合的值」与「右表达式所有组合的值」两两运算。
﻿
具体实现﻿
理清思路后，有没有暗暗感觉到这是一道递归算法题，因为子表达式也以相同方式进行分解组合。
﻿
实现就比较简单了，但是要注意几个地方。
表达式分解后，对数字的判断。因为这里我犯了个低级的错误，受题目栗子影响，误认为当表达式长度为 1 时就是数字。(⊙o⊙)。
考虑当表达式不存在操作符时的边界条件。这时不能将表达式分为两部分，要注意这里的处理。
可将表达式计算的结果缓存，防止重复计算。
﻿
核心代码如下：
// start 代表字符串左边界，end 代表字符串右边界
var recursive2 = function (input, start, end) {
    if (start < 0 || end > input.length || start > end) 
    {
        return []
    }
﻿
	// 取出子表达式
    const substr = input.slice(start, end + 1)
﻿
    // 如果有缓存
    if (map.has(substr)) {
        return map.get(substr)
    }
﻿
    let resultList = []
    let i = start
    while (i <= end) {
        const op = input[i]
        if (op === '+' || op === '-' || op === '*') {
	        // 分别计算左/右两边的值
            const leftPartResult = recursive(input, start, i - 1)
            const rightPartResult = recursive(input, i + 1, end)
﻿
			// 运算符函数
            const opFunc = opMap[op]
﻿
            // 两个数组做运算
            leftPartResult.forEach(left => {
                rightPartResult.forEach(right => {
                    const result = opFunc(left, right)
                    resultList.push(result)
                })
            });
        }
﻿
        i += 1
    }
﻿
    // 说明是数字
    if (resultList.length === 0) {
	    // 以 [num] 方式返回
        resultList.push(parseInt(substr))
    }
    
    // 缓存
    map.set(substr, resultList)
﻿
    return resultList
}
﻿
完整代码可点此查看。
﻿
发布于: 2020 年 05 月 24 日阅读数: 30
原文链接:【http://xie.infoq.cn/article/0783fe30cf3f9fac00b381061】。
liu_liu

 关注
不要相信自己的记忆力 2017.11.13 加入
还未添加个人简介
发布
暂无评论