LeetCode 20: Valid Parentheses (Stack Matching)
LeetCode 20StringStackToday we solve LeetCode 20 - Valid Parentheses.
Source: https://leetcode.com/problems/valid-parentheses/
English
Problem Summary
Given a string s containing only ()[]{}, determine whether the input string is valid.
A string is valid if: every opening bracket has a corresponding closing bracket of the same type, and closing order is correct.
Key Insight
The most recent unmatched opening bracket must be closed first. This is exactly LIFO, so a stack is the natural structure.
Brute Force and Limitations
Repeatedly removing pairs like (), [], {} from the string can work conceptually, but repeated scans/rebuilds are inefficient and may degrade to O(n^2).
Optimal Algorithm Steps
1) Initialize an empty stack.
2) Traverse characters left to right.
3) If char is opening bracket, push to stack.
4) If char is closing bracket, stack must be non-empty and top must match its type; then pop.
5) After traversal, stack must be empty for the string to be valid.
Complexity Analysis
Time: O(n).
Space: O(n) in worst case.
Common Pitfalls
- Popping without checking stack emptiness.
- Comparing wrong bracket pairs.
- Forgetting to ensure stack is empty at the end.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public boolean isValid(String s) {
char[] st = new char[s.length()];
int top = -1;
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
st[++top] = c;
} else {
if (top < 0) return false;
char open = st[top--];
if ((c == ')' && open != '(') ||
(c == ']' && open != '[') ||
(c == '}' && open != '{')) {
return false;
}
}
}
return top == -1;
}
}func isValid(s string) bool {
stack := make([]rune, 0, len(s))
for _, c := range s {
if c == '(' || c == '[' || c == '{' {
stack = append(stack, c)
} else {
if len(stack) == 0 {
return false
}
open := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if (c == ')' && open != '(') ||
(c == ']' && open != '[') ||
(c == '}' && open != '{') {
return false
}
}
}
return len(stack) == 0
}class Solution {
public:
bool isValid(string s) {
vector<char> st;
st.reserve(s.size());
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push_back(c);
} else {
if (st.empty()) return false;
char open = st.back();
st.pop_back();
if ((c == ')' && open != '(') ||
(c == ']' && open != '[') ||
(c == '}' && open != '{')) {
return false;
}
}
}
return st.empty();
}
};class Solution:
def isValid(self, s: str) -> bool:
stack = []
for c in s:
if c in '([{':
stack.append(c)
else:
if not stack:
return False
open_br = stack.pop()
if (c == ')' and open_br != '(') or \
(c == ']' and open_br != '[') or \
(c == '}' and open_br != '{'):
return False
return len(stack) == 0var isValid = function(s) {
const stack = [];
for (const c of s) {
if (c === '(' || c === '[' || c === '{') {
stack.push(c);
} else {
if (!stack.length) return false;
const open = stack.pop();
if ((c === ')' && open !== '(') ||
(c === ']' && open !== '[') ||
(c === '}' && open !== '{')) {
return false;
}
}
}
return stack.length === 0;
};中文
题目概述
给定只包含 ()[]{} 的字符串 s，判断其括号是否有效：每个左括号要有同类型右括号，并且闭合顺序正确。
核心思路
“最后出现、最先匹配”天然是栈模型（LIFO）。遇到左括号入栈，遇到右括号必须匹配栈顶。
暴力解法与不足
可以反复删除字符串中的 ()/[]/{}，直到无法删除再判断是否为空串。思路直观，但多次扫描与构造字符串，效率较低，最坏接近 O(n^2)。
最优算法步骤
1）初始化空栈。
2）遍历字符串。
3）左括号入栈。
4）右括号时要求栈非空且类型匹配，然后弹栈。
5）遍历结束后栈为空则有效，否则无效。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)（最坏全是左括号）。
常见陷阱
- 栈空时直接弹栈导致错误。
- 括号匹配关系写反或遗漏。
- 忘记最终检查栈是否清空。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public boolean isValid(String s) {
char[] st = new char[s.length()];
int top = -1;
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
st[++top] = c;
} else {
if (top < 0) return false;
char open = st[top--];
if ((c == ')' && open != '(') ||
(c == ']' && open != '[') ||
(c == '}' && open != '{')) {
return false;
}
}
}
return top == -1;
}
}func isValid(s string) bool {
stack := make([]rune, 0, len(s))
for _, c := range s {
if c == '(' || c == '[' || c == '{' {
stack = append(stack, c)
} else {
if len(stack) == 0 {
return false
}
open := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if (c == ')' && open != '(') ||
(c == ']' && open != '[') ||
(c == '}' && open != '{') {
return false
}
}
}
return len(stack) == 0
}class Solution {
public:
bool isValid(string s) {
vector<char> st;
st.reserve(s.size());
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push_back(c);
} else {
if (st.empty()) return false;
char open = st.back();
st.pop_back();
if ((c == ')' && open != '(') ||
(c == ']' && open != '[') ||
(c == '}' && open != '{')) {
return false;
}
}
}
return st.empty();
}
};class Solution:
def isValid(self, s: str) -> bool:
stack = []
for c in s:
if c in '([{':
stack.append(c)
else:
if not stack:
return False
open_br = stack.pop()
if (c == ')' and open_br != '(') or \
(c == ']' and open_br != '[') or \
(c == '}' and open_br != '{'):
return False
return len(stack) == 0var isValid = function(s) {
const stack = [];
for (const c of s) {
if (c === '(' || c === '[' || c === '{') {
stack.push(c);
} else {
if (!stack.length) return false;
const open = stack.pop();
if ((c === ')' && open !== '(') ||
(c === ']' && open !== '[') ||
(c === '}' && open !== '{')) {
return false;
}
}
}
return stack.length === 0;
};
Comments