20. 有效的括号
题目描述
输入字符串 s，它只由 '('、')'、'['、']'、'{'、'}' 六种字符组成。
满足下面三条时，s 是有效的：每个左括号都由同类型的右括号关闭；后打开的左括号要先关闭；每个右括号前面都有一个同类型的左括号与之配对。
有效时返回 true，否则返回 false。
示例 1
输入：s = "()" 输出：true
示例 2
输入：s = "()[]{}"
输出：true解释：三对括号依次各自配对。
示例 3
输入：s = "(]" 输出：false
解释：'(' 遇到的是 ']'，类型不同。
示例 4
输入：s = "([])" 输出：true
解释：[] 嵌在 () 里，配对顺序正确。
示例 5
输入：s = "([)]" 输出：false
解释：'[' 还没关闭时就出现了 ')'，顺序交错。
数据范围
1 <= s.length <= 10^4s只含括号字符'()[]{}'。
解题思路
左括号入栈，右括号匹配栈顶。
为什么正确
栈保存尚未闭合的左括号。
复杂度分析
时间 O(n)，额外空间 O(n)。
易错点
注意边界条件并在回溯或弹出后恢复状态。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def isValid(self,s):
p={')':'(',']':'[','}':'{'};st=[]
for c in s:
if c in '([{':st.append(c)
elif not st or st.pop()!=p[c]:return False
return not stclass Solution {
public boolean isValid(String s) {
Map<Character, Character> p = Map.of(')', '(', ']', '[', '}', '{');
Deque<Character> st = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') st.push(c);
else if (st.isEmpty() || !st.pop().equals(p.get(c))) return false;
}
return st.isEmpty();
}
}class Solution {
public:
bool isValid(string s) {
unordered_map<char, char> p = {{')', '('}, {']', '['}, {'}', '{'}};
vector<char> st;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') st.push_back(c);
else {
if (st.empty() || st.back() != p[c]) return false;
st.pop_back();
}
}
return st.empty();
}
};func isValid(s string) bool {
p := map[byte]byte{')': '(', ']': '[', '}': '{'}
st := []byte{}
for i := 0; i < len(s); i++ {
c := s[i]
if c == '(' || c == '[' || c == '{' {
st = append(st, c)
} else if len(st) == 0 || st[len(st)-1] != p[c] {
return false
} else {
st = st[:len(st)-1]
}
}
return len(st) == 0
}var isValid = function(s) {
const p = { ')': '(', ']': '[', '}': '{' }, st = [];
for (const c of s) {
if ('([{'.includes(c)) st.push(c);
else if (!st.length || st.pop() !== p[c]) return false;
}
return st.length === 0;
};function isValid(s: string): boolean {
const p: Record<string, string> = { ')': '(', ']': '[', '}': '{' }, st: string[] = [];
for (const c of s) {
if ('([{'.includes(c)) st.push(c);
else if (!st.length || st.pop() !== p[c]) return false;
}
return st.length === 0;
};