1 / 4思路
Valid Parentheses
思路
左括号入栈;右括号必须和栈顶配对。扫描结束后栈为空才算有效。用映射表把三种右括号映射到对应的左括号,避免写三段分支。
复杂度
- 时间 O(n):每个字符进出栈一次。
- 空间 O(n):最坏全是左括号。
代码
- Python
- TypeScript
def is_valid(s: str) -> bool:
pairs = {")": "(", "]": "[", "}": "{"}
stack: list[str] = []
for char in s:
if char in pairs:
if not stack or stack.pop() != pairs[char]:
return False
else:
stack.append(char)
return not stack
function isValid(s: string): boolean {
const pairs: Record<string, string> = {')': '(', ']': '[', '}': '{'};
const stack: string[] = [];
for (const char of s) {
if (char in pairs) {
if (stack.pop() !== pairs[char]) return false;
} else {
stack.push(char);
}
}
return stack.length === 0;
}
边界
- 奇数长度:一定无效,可提前返回。
- 先出现右括号:栈为空,返回 false。
- 只有左括号:扫描结束栈非空,返回 false。