LeetCode: 20 Valid Parentheses

Given a string s containing just the characters (, ), {, }, [ and ], determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Example:

Input: s = "()"
Output: true

Example:

Input: s = "()[]{}"
Output: true

Example:

Input: s = "(]"
Output: false

问题

给定一个仅包含字符 (、)、{、}、[ 和 ] 的字符串 s，判断输入的字符串是否有效。

一个输入字符串是有效的，需满足以下条件：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

解决方案 1

使用栈

Approach 1 / 方法 1

This solution uses a stack to ensure that each opening bracket has a corresponding closing bracket in the correct order. The stack keeps track of the open brackets, and as we encounter a closing bracket, we check if it matches the most recent open bracket on top of the stack.

该解决方案使用栈来确保每个开括号都有一个相应的闭括号，并且顺序正确。栈用来跟踪未闭合的开括号，当遇到闭括号时，我们检查它是否与栈顶最近的开括号匹配。

Implementation / 实现

python

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        mapping = {')': '(', '}': '{', ']': '['}

        for char in s:
            if char in mapping:
                top_element = stack.pop() if stack else '#'

                if mapping[char] != top_element:
                    return False
            else:
                stack.append(char)

        return not stack

Explanation / 解释

1. Initialize a Stack and Mapping / 初始化栈和映射

   stack = []
   mapping = {')': '(', '}': '{', ']': '['}

   • English: We initialize an empty stack to keep track of opening brackets. We also create a mapping of closing brackets to their corresponding opening brackets.
   • Chinese: 我们初始化一个空栈来跟踪开括号。同时，我们创建一个映射，将闭括号与其对应的开括号关联。

2. Iterate Over Each Character in the String / 遍历字符串中的每个字符

   for char in s:

   • English: We iterate over each character in the string s.
   • Chinese: 我们遍历字符串 s 中的每个字符。

3. Check if Character is a Closing Bracket / 检查字符是否为闭括号

   if char in mapping:

   • English: We check if the current character is a closing bracket by looking it up in the mapping.
   • Chinese: 我们通过在 mapping 中查找当前字符来检查它是否为闭括号。

4. Pop the Top Element of the Stack / 弹出栈顶元素

   top_element = stack.pop() if stack else '#'

   • English: We pop the top element from the stack if it’s not empty; otherwise, we use # as a placeholder.
   • Chinese: 如果栈不为空，我们弹出栈顶元素；否则，使用 # 作为占位符。

5. Check if the Mapping Matches the Top Element / 检查映射是否与栈顶元素匹配

   if mapping[char] != top_element:
      return False

   • English: We check if the popped element matches the expected opening bracket from the mapping. If it doesn’t, the string is invalid, so we return False.
   • Chinese: 我们检查弹出的元素是否与映射中预期的开括号匹配。如果不匹配，则字符串无效，我们返回 False。

6. Append Opening Brackets to the Stack / 将开括号添加到栈中

   else:
      stack.append(char)

   • English: If the character is not a closing bracket, it’s an opening bracket, so we push it onto the stack.
   • Chinese: 如果该字符不是闭括号，则它是开括号，我们将其推入栈中。

7. Final Check: Is the Stack Empty? / 最后检查：栈是否为空？

   return not stack

   • English: Finally, we check if the stack is empty. If it is, then all the brackets were matched correctly, so we return True. If not, we return False.
   • Chinese: 最后，我们检查栈是否为空。如果是，则所有括号都正确匹配，我们返回 True。如果不是，我们返回 False。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(n), where n is the length of the string s. We process each character once.
• Space Complexity / 空间复杂度: O(n), where n is the length of the string s. In the worst case, all the characters are opening brackets, and they are pushed onto the stack.

Key Concept / 关键概念

• Stack Usage / 栈的使用: The stack is crucial for keeping track of opening brackets and ensuring that each closing bracket matches the correct opening bracket.
• 栈的使用: 栈对于跟踪开括号并确保每个闭括号与正确的开括号匹配至关重要。

Summary / 总结

• English: The stack-based approach efficiently handles the validation of parentheses by ensuring that every opening bracket has a corresponding closing bracket in the correct order.
• Chinese: 基于栈的方法通过确保每个开括号都有一个顺序正确的闭括号，来高效地处理括号的验证。

Tips / 提示

• English: Pay attention to edge cases like empty strings or strings with only opening or closing brackets.
• Chinese: 注意边界情况，如空字符串或只有开括号或闭括号的字符串。

Solution Template for Similar Questions / 提示

• English: Use a stack to handle problems involving nested structures, such as parentheses, brackets, or tags.
• Chinese: 使用栈来处理涉及嵌套结构的问题，如括号、方括号或标签。

5 More Similar Questions / 推荐5问题

1. LeetCode 22. Generate Parentheses
2. LeetCode 32. Longest Valid Parentheses
3. LeetCode 71. Simplify Path
4. LeetCode 394. Decode String
5. LeetCode 856. Score of Parentheses

Recommended Resources / 推荐资源

LeetCode #20: Valid Parentheses | Stack Data Structure by Algo Engine