20. 有效的括号
查看题目简单
字符串
高频
解法一：栈
时间复杂度：O(n) | 空间复杂度：O(n) | 推荐使用
动画演示
有效的括号 - 动画演示
准备就绪 - 输入括号字符串，然后点击开始
(
)
[
]
{
}
}
栈状态：
空栈
代码实现
import java.util.HashMap;
import java.util.Stack;
class Solution {
public boolean isValid(String s) {
if (s == null) {
return true;
}
HashMap<Character, Character> keyWords = new HashMap<>();
keyWords.put(')', '(');
keyWords.put(']', '[');
keyWords.put('}', '{');
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (!stack.empty()) {
if (stack.peek() == keyWords.get(c)) {
stack.pop();
continue;
}
}
stack.push(c);
}
return stack.empty();
}时间复杂度：O(n)
空间复杂度：O(n)
算法思路：
使用栈数据结构解决有效的括号问题，这是栈的经典应用场景。
核心思想：
1. 遍历字符串，遇到左括号（(、[、{）则入栈
2. 遇到右括号（)、]、}）则检查栈顶元素是否匹配
3. 如果匹配，栈顶元素出栈，继续遍历
4. 如果不匹配，直接返回false
5. 遍历结束后，若栈为空则括号有效，否则无效
复杂度分析：
- 时间复杂度：O(n)，只需遍历字符串一次
- 空间复杂度：O(n)，最坏情况下需要存储所有左括号到栈中
解法二：string-replace
时间复杂度：O(n^2) | 空间复杂度：O(n)
动画演示
有效的括号 - 字符串替换法动画演示
准备就绪 - 输入括号字符串，然后点击开始
步骤：0
当前字符串：
(
)
[
]
{
}
}
替换后：
(
)
[
]
{
}
}
代码实现
class Solution {
public boolean isValid(String s) {
if (s == null) {
return true;
}
// 字符串替换法：不断替换匹配的括号对，直到无法再替换为止
while (s.contains("()") || s.contains("[]") || s.contains("{}")) {
s = s.replace("()", "").replace("[]", "").replace("{}", "");
}
return s.length() == 0;
}时间复杂度：O(n^2)
空间复杂度：O(n)
算法思路：
使用字符串替换法解决有效的括号问题，通过不断替换匹配的括号对，直到无法再替换为止。
核心思想：
1. 遍历字符串，查找并替换所有匹配的括号对（()、[]、{}）
2. 重复上述过程，直到字符串中不再包含任何匹配的括号对
3. 最后检查字符串是否为空，若为空则括号有效，否则无效
复杂度分析：
- 时间复杂度：O(n^2)，每次替换操作需要遍历整个字符串，最坏情况下需要执行n/2次替换
- 空间复杂度：O(n)，替换过程中需要创建新的字符串