栈的应用

LARRY1024 / 2023-09-11 / 原文

应用
- 应用1：Leetcode 678. 有效的括号字符串
  - 题目
  - 分析
    - 方法一：栈
    - 方法二：动态规划
  - 代码实现

应用

应用1：Leetcode 678. 有效的括号字符串

题目

678. 有效的括号字符串

分析

方法一：栈

维护两个栈：$stack_1$ 和 $stack_2$，分别保存左括号元素的下标和星号元素的下标。

遍历字符串，

遇到一个左括号，就将其下标压入 $stack_1$；
遇到一个左括号，就将其下标压入 $stack_2$；
如果遇到一个右括号
- 如果 $stack_1$ 不为空，则弹出一个左括号的下标；
- 如果 $stack_2$ 不为空，则弹出一个星号的下标；
- 如果 $stack_1$ 和 $stack_2$ 都为空，则返回 $False$;
如果右括号适配完之后，$stack_1$ 和 $stack_2$ 中都还有元素
- 如果 $stack_1$ 和 $stack_2$ 中的元素个数相等，判断两个栈的栈底的元素组合是否满足有效括号的条件；
- 如果 $stack_1$ 中的元素个数大于 $stack_2$，则返回 $False$ ；
- 如果 $stack_1$ 中的元素个数小于 $stack_2$，则返回 $True$ ；

方法二：动态规划

代码实现

方法一：

class Solution:
    def checkValidString(self, s: str) -> bool:
        # 保存左括号的下标
        stack1 = list()
        # 保存星号的下标
        stack2 = list()
        # 遇到左括号和星号，分别将其入栈; 遇到右括号，则优先弹出一个左括号，否则弹出一个星号
        for index, char in enumerate(s):
            if char == "(":
                stack1.append(index)
            elif char == "*":
                stack2.append(index)
            else:
                if stack1:
                    stack1.pop()
                elif stack2:
                    stack2.pop()
                else:
                    return False

        # 如果栈里还剩余星号和左括号
        while stack1 and stack2:
            index1 = stack1.pop()
            index2 = stack2.pop()
            # 栈底的元素
            if index1 > index2:
                return False

        # 栈里还有左括号，返回False
        if stack1:
            return False

        return True

复杂度：