巧解有效括号

发表于 分类于 ，

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

  1. 任何左括号 ( 必须有相应的右括号)。
  2. 任何右括号 ) 必须有相应的左括号 ( 。

  3. 左括号 ( 必须在对应的右括号之前 )。

  4. *可以被视为单个右括号) ，或单个左括号 ( ，或一个空字符串。

  5. 一个空字符串也被视为有效字符串。

(Leetcode.678)

测试：

1
2
3
4
5
6
7
8
"()"
"(*)"
"(*))"
"**()()"
"*"
"("
")"
"()(*)*))"

输出：

1
2
3
4
5
6
7
8
true
true
true
true
true
false
false
true

解法一(栈)

使用两个栈来分别存放左括号(和*，基本步骤如下：

  • 遇到左括号时，存放左括号的栈此左括号的索引下标入栈；
  • 遇到星号时，存放星号的栈将此星号的索引下标入栈；
  • 遇到右括号时，优先弹出左括号的栈顶元素；
  • 如果左括号栈为空，弹出星号的栈顶元素；
  • 如果星号的栈也为空，而此时还有新的右括号，说明不能构成有效的括号对；
  • 如果字符串遍历完后左括号的栈不为空，则需要取星号栈中的星号来当做右括号与其配对，此时需要注意，星号栈中的索引值必须大于左括号栈中的元素的索引值；
  • 如果最终可以将所用左括号配对完毕，则是一个有效的字符括号对。

在存取的时候要注意将左括号与星号的索引值入栈，在右括号匹配的时候，因为栈中的元素索引是严格小于当前元素的索引的，此时右括号一定在所有元素的右边，所以不必要对比索引大小，直接按照优先级进行出栈配对即可。而最终在对比左括号和星号的配对情况的时候，星号如果出现在左括号的左边，则不能组合成一个有效的括号对，所以需要额外对比他们的索引值。

示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def checkValidString(self, s: str) -> bool:
        stack1 = [] # 存放星号索引
        stack2 = [] # 存放左括号索引
        for i in range(len(s)):
            if s[i] == '(':
                stack1.append(i) # (
            elif s[i]=='*':
                stack2.append(i) # *
            else:
                if stack1: # 优先弹出左括号
                    stack1.pop()
                elif stack2:
                    stack2.pop()
                else: # 两者皆空，右括号超标，直接返回
                    return False
        if stack1==[]:
            return True
        else: # 当左括号还有剩余时
            while stack1:
                if stack2==[]: # 没有足够的星号，直接返回
                    return False
                t1 = stack1.pop()
                t2 = stack2.pop()
                if t2>t1: # 星号的索引必须大于左括号的索引
                    continue
                else:
                    return False
        return True

解法二(贪心)

采用两个变量left_max,left_min记录未配对的左括号的最大值和最小值，

  • 当遇到左括号时，最大值(left_max)加一，最小值(left_min)加一；
  • 当遇到右括号时，最大值减一，最小值减一；
  • 当遇到星号时，最大值加一，最小值减一；
  • 当最小值小于0时，将其赋0，保持非负；
  • 当最大值小于0时，构成无效括号对，直接返回；
  • 遍历完成后左括号的数量为0说明括号对有效；

遇到左括号和右括号的计算方式很好理解，直接严格加减一就可以了，遇到星号由于其可以代表左括号。右括号和普通字符串，所以最大值加一、最小值减一；在遍历过程中如果需要将最小值设置为非负，这是要保证未匹配的左括号总是大于等于0的；当最大值也降到0以下，则说明无论如何改变星号也不能弥补左括号的不足，所以返回False.

示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def checkValidString(self, s: str) -> bool:
        left_max = 0
        left_min = 0
        for c in s:
            if c=='(':
                left_max += 1
                left_min += 1
            elif c==")":
                left_max -= 1
                left_min -= 1
            else:
                left_max += 1
                left_min -= 1
            if left_max<0:
                return False
            left_min = max(left_min,0)
        return not left_min