@(LeetCode)
问题描述
给定一个括号对匹配的字符串，计算总分数，其中规则如下：
-
()表示1分 -
AB表示A+B分，其中A和B都是括号匹配的字符串 -
(A)表示2 * A分，其中A是括号匹配的字符串
栗 1：
输入："()"
输出：1
栗 2：
输入："(())"
输出：2
解释：
属于 (A) 模式，2 * 1 = 2
栗 3：
输入："()()"
输出：2
解释：
属于 A+B 模式，1 + 1 = 2
栗 4：
输入："(()(()))"
输出：6
解释：
一层层计算：2 * （1 + 2 * 1）= 6
注意：
-
S是括号匹配的字符串，只包括(和) 2 <= S.length <= 50
解题思路
递归解法
题意很明确，三种模式的字符串任意组合，求总分数。
-
AB模式为A + B，那只需要分别求出A和B即可。 -
(A)模式为2 * A，需要计算出A。 -
()为最小原子串，分数为1。
由于只知道 () 的值，因此最终目标是将整个字符串拆分至最小原子串。
字符串的组成规律比较明显，AB 可以看成 A、B 两个分组，(A) 拆分出 A 即可。因此可根据括号匹配情况分组，组内再一层层进行拆分，最后拆分至 () 。在拆分过程中识别出 * 2，还是相加求和。
举个栗子，假设 S = (())()(()(()))。
其分解过程如下图所示：
QQ20200307-160007@2x.png
-
S中有三个分组，(())、()和(()(()))。一个分组的定义就是最外层(和)匹配的字符串，不包括内层。那么如何找到
S中的所有匹配分组？
从第一个(开始遍历，找到其对应的)，此时得到一个分组。若)不是最后一个字符，则从)的下一个位置继续找下一分组。 -
依次处理分组求和。
- 若分组为最小单元
()，直接返回1。 - 若分组不为最小单元，则继续拆分。比如
(()(()))，则拆分为2 * ()(())，然后()(())继续按照1的步骤重复处理。
拆分过程中最重要的一个点就是：
- 当匹配字符串为
()时，直接返回 1。 - 其他情况，都是
(A)模式，按2 * A的方式处理。
以上处理过程，其实就是递归处理的方式。不断的进行拆分，直至为最小单元。
思路总结如下：
- 按括号匹配进行分组，得到
n个分组，A + B + C + ... - 分别处理
A、B、C、... - 若分组其为
()，则返回1；否则进行2 * A处理，对A的处理又从第一步开始。
递归代码如下：
var scoreOfParentheses = function(S) {
return dfs(0, S.length - 1, S)
};
var dfs = function(l, r, S) {
if (l < r && r < S.length) {
// 从 l 开始遍历，寻找最右匹配 )
let start = l
let i = l
let list = []
let sum = 0
// l-r 之间可能有多组，用 sum 来保存每组值之和
while (i <= r) {
// 计算匹配括号
if (S[i] === '(') {
list.push(S[i])
} else if (S[i] === ')') {
list.pop()
// 找到匹配的 )
if (list.length === 0) {
// () 模式，直接加 1
if (i - start === 1) {
sum += 1
} else {
// (A) 模式，取到 A，继续处理。去除括号，左边+1，右边-1
sum += 2 * dfs(start + 1, i - 1, S)
}
// 下一分组开始
start = i + 1
}
}
i += 1
}
return sum
}
return 0
}
栈的解法
使用栈来保存当前已匹配字符串的总分数，这种解法也比较巧妙。
- 当遇到
(，进栈0； - 当遇到
)，表示匹配，计算到当前为止的总分数，即前面的总分数+当下的分数。因为以)结束时，有可能是2倍的分数，而当下的分数至少为1，所以取两者的最大值：score = pre + max(2 * cur, 1)。
举个简单的栗子。假设 S = '()'，栈初始值为 [0]。
- 遇到
(，0进栈，栈为[0, 0]。 - 遇到
)，计算分数。出栈2个元素，分别为pre = 0和cur = 0，则score = 0 + max(2 * 0, 1) = 1。将其进栈，栈为[1]。 - 遍历结束，最终栈中的元素为总分数。
再来个复杂点的。假设S = '()(())'，栈初始值为 [0]。
- 遇到
(，0进栈，栈为[0, 0]。 - 遇到
)，计算分数。出栈2个元素，分别为pre = 0和cur = 0，则score = 0 + max(2 * 0, 1) = 1。将总分数进栈，栈为[1]。 - 遇到
(，0进栈，栈为[1, 0]。 - 遇到
(，0进栈，栈为[1, 0, 0]。 - 遇到
)，计算分数。出栈2个元素，分别为pre = 0和cur = 0，则score = 0 + max(2 * 0, 1) = 1。将总分数进栈，栈为[1, 1]。 - 遇到
)，计算分数。出栈2个元素，分别为pre = 1和cur = 1，则score = 1 + max(2 * 1, 1) = 3。将总分数进栈，栈为[3]。 - 遍历结束，最终栈中的元素为总分数
3。
代码如下：
// 使用栈的方式
var scoreOfParentheses2 = function(S) {
let stack = new Array()
stack.push(0)
let i = 0
while (i < S.length) {
if (S[i] === '(') {
stack.push(0)
} else {
// 计算分数
const cur = stack.pop()
const pre = stack.pop()
const score = pre + Math.max(2 * cur, 1)
stack.push(score)
}
i += 1
}
return stack[0]
};
根据深度求解
这种解法也比较有新意，它将字符串表示为树型结构。
如果是 AB 模式，则表示 A 和 B 是兄弟节点；如果是(A) 模式，表示父子节点。字符串的分解图跟第一种解法的类似。
比如 S = '(()(()()))'，其可被分解为：
(10) 第 0 层
／ \
(1) (4) 第 1 层
/ \
(1) (1) 第 2 层
总分数 = 2^1 + 2^2 + 2^2 = 10。
主要思路就是求出各个最小原子单元 () 所在的层数 l，然后整体求和 2^l 即可。
代码如下：
// 使用树形结构计算
var scoreOfParentheses3 = function(S) {
let i = 0
let sum = 0
let layer = 0
while (i < S.length) {
// 计算层数
if (S[i] === '(') {
layer += 1
} else {
layer -= 1
}
// 最小原子字符串 ()，根据层数计算分数
if (S[i] === ')' && S[i - 1] === '(') {
sum += 1 << layer
}
i += 1
}
return sum
}
网友评论