基本信息

  • 题号：678
  • 题厂：脸书
  • 难度系数：中


字符串由 （ ， ），*组成，如果有效返回 True，无效返回 False……

那什么是有效的字符串？？？

  • 圆括号（）成对出现，即 （ 要出现在 ）的前面
  • * 可以根据情况替换为 （ 或 ）或 空字符串
例如 s = "(*)"
返回 True， 这时把 * 当作空字符串 

再例如 s = "(*))" 
同样返回 True，这时要把 * 当作 （ 与后面的 ）配对


解题思路

  • 字符括号配对题，首先想到 stack：当遇到 （ 时，把 （ 存入 stack，遇到 ） 时再从 stack pop 出来与之配对
  • 为了实现更多配对，优先从 （ 里面配对，没有 （ 时再从 * 里面配对。所以需要准备两个 stack 分别存 （ 和 *
  • 当 ） 完成配对后，（ 如果有剩，还需要把剩余 （ 与 * 配对
class Solution:
    def checkValidString(self, s: str) -> bool:
        # 创建 2 个 stack，分别存出现（ 和 * 的 index
        left = []
        star = []
        
        # 遍历字符串时，如果遇上（ 或 *，将它们存入 stack
        # 遇上 ）时，优先于（ 配对，再和 * 配对。如果（ 和 * 都无法配对，可提前返回 False
        for i in range(len(s)):
            if s[i] == "(":
                left.append(i)
            elif s[i] == "*":
                star.append(i)
            else:
                if left:
                    left.pop()
                elif star:
                    star.pop()
                else:
                    return False
                
        # i: index left; j: index star
        i = j = 0
        # 如果（ 还有剩，再 * 配对，此时 * 当做 ）使用
        # 能与（ 配对的 * 需要满足 index 大于 star。如果不能满足，可以提前返回 False
        while i < len(left):
            while j < len(star) and star[j] < left[i]:
                j += 1
            
            # find a pair of (*, move both i and j 
            if j < len(star) and star[j] > left[i]:
                i += 1
                j += 1
            else:
                return False
        
        return True


Constraints

  • 1 <= s.length <= 100
  • s[i] is '(', ')' or '*'.


Big O

  • Time：O（n）
  • Space：O（n）创建了 stack



测试

  • 字符串为 1 时

……


总结

  • 简单档 stack 组装变形「贪心」后升级成了中档！！！