Valid Parentheses（有效的括号）

题目 / Problem

中文： 给定一个只包含 '('、')'、'{'、'}'、'[' 和 ']' 的字符串 s，判断该字符串是否有效。

English: Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine whether 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.
3. 每个右括号都有一个对应的、类型相同的左括号。
   Every closing bracket has a corresponding opening bracket of the same type.

示例 / Examples

Example 1

Input:  s = "()"
Output: true

Example 2

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

Example 3

Input:  s = "(]"
Output: false

Example 4

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

Example 5

Input:  s = "([)]"
Output: false

约束 / Constraints

• 1 <= s.length <= 10⁴
• s 只包含括号字符 '()[]{}'。
  s consists only of parentheses '()[]{}'.

解题思路：栈 / Approach: Stack

括号匹配具有“后打开的括号先闭合”的特点，符合栈的后进先出规则。
Bracket matching follows a “last opened, first closed” pattern, which matches the last-in, first-out behavior of a stack.

遍历字符串中的每个字符：
Iterate through every character in the string:

1. 如果当前字符是左括号，将它压入栈中。
   If the current character is an opening bracket, push it onto the stack.
2. 如果当前字符是右括号，弹出栈顶的左括号。
   If it is a closing bracket, pop the opening bracket from the top of the stack.
3. 如果栈为空，或者弹出的左括号与当前右括号不匹配，返回 false。
   If the stack is empty or the popped opening bracket does not match the closing bracket, return false.
4. 遍历结束后，如果栈为空，说明所有括号均已正确匹配；否则仍有未闭合的左括号。
   After traversal, an empty stack means all brackets were matched; otherwise, some opening brackets remain unclosed.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {string} s
 * @return {boolean}
 */
function isValid(s) {
  const stack = [];
  const pairs = {
    ')': '(',
    ']': '[',
    '}': '{',
  };

  for (const char of s) {
    if (char === '(' || char === '[' || char === '{') {
      stack.push(char);
      continue;
    }

    if (stack.pop() !== pairs[char]) {
      return false;
    }
  }

  return stack.length === 0;
}

执行过程 / Walkthrough

以 s = "([])" 为例：
For s = "([])":

遍历完成后栈为空，因此返回 true。
The stack is empty after traversal, so return true.

为什么 "([)]" 无效？ / Why Is "([)]" Invalid?

读取 ) 时，栈顶是 [，但 ) 只能与 ( 匹配。括号闭合顺序错误，因此返回 false。
When ) is read, the top of the stack is [, but ) can only match (. The closing order is incorrect, so return false.

复杂度 / Complexity

• 时间复杂度：O(n)，字符串中的每个字符只处理一次。
  Time: O(n), because every character is processed once.
• 空间复杂度：O(n)，最坏情况下所有字符都是左括号。
  Space: O(n), because all characters may be opening brackets in the worst case.

易错点 / Common Pitfalls

• 不能只统计左右括号的数量，还必须检查括号类型和闭合顺序。
  Counting brackets is not enough; their types and closing order must also match.
• 遇到右括号时，如果栈为空，应立即返回 false。
  If a closing bracket is encountered while the stack is empty, return false immediately.
• 遍历结束后必须检查栈是否为空。
  Always verify that the stack is empty after traversal.
• "([)]" 中每种括号的数量相等，但闭合顺序错误。
  In "([)]", the bracket counts match, but the closing order is invalid.