有效的括号
难度:
标签:
题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()" 输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]" 输出：false
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
代码结果
运行时间: 36 ms, 内存: 15 MB
/*
* 思路：
* 1. 使用栈和Java Stream来验证括号的有效性。
* 2. 使用Stream的forEach方法遍历字符串中的每个字符。
* 3. 遇到左括号时入栈，遇到右括号时检查栈顶元素是否匹配，若不匹配则返回false。
*/
import java.util.Stack;
public class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
s.chars().forEach(c -> {
char ch = (char) c;
if (ch == '(' || ch == '{' || ch == '[') {
stack.push(ch);
} else {
if (stack.isEmpty() || (ch == ')' && stack.pop() != '(') ||
(ch == '}' && stack.pop() != '{') || (ch == ']' && stack.pop() != '[')) {
throw new RuntimeException("Invalid");
}
}
});
return stack.isEmpty();
}
}解释
方法:
这个题解使用了栈的数据结构来判断括号的有效性。具体思路如下：
1. 首先判断字符串长度是否为奇数，如果是奇数则一定不是有效的括号，直接返回 false。
2. 计算字符串长度的一半 half，作为左括号数量的上限。
3. 遍历字符串中的每个字符：
- 如果当前字符是左括号，则将其压入栈中，并检查栈的大小是否超过 half，如果超过则说明左括号数量过多，直接返回 false。
- 如果当前字符是右括号，则检查栈是否为空，如果为空则说明没有与之匹配的左括号，直接返回 false。然后检查栈顶元素是否与当前右括号匹配，如果不匹配则直接返回 false，否则将栈顶元素弹出。
4. 遍历完成后，检查栈是否为空，如果为空则说明所有括号都正确匹配，返回 true，否则返回 false。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在判断字符串长度为奇数时直接返回false，有什么数学或逻辑上的依据吗？
▷🦆
在您的解法中提到，如果栈的大小超过一半，则返回false。能否详细解释为什么栈的大小超过字符串长度的一半就可以确定字符串不是有效的括号序列？
▷🦆
您在处理右括号不匹配的情况时，只是直接返回false。在实际应用中，是否考虑过提供更具体的错误信息来帮助定位问题？
▷🦆
在算法的最后，您检查栈是否为空来确定所有括号是否匹配。如果栈非空，是否可以通过查看栈中剩余元素来获取更多关于错误的详细信息？
▷相关问题
括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1 输出：["()"]
提示：
1 <= n <= 8
最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"
示例 3：
输入：s = "" 输出：0
提示：
0 <= s.length <= 3 * 104s[i]为'('或')'
删除无效的括号
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()" 输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()" 输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
提示：
1 <= s.length <= 25s由小写英文字母以及括号'('和')'组成s中至多含20个括号
检查替换后的词是否有效
给你一个字符串
s ，请你判断它是否 有效 。
字符串 s 有效 需要满足：假设开始有一个空字符串 t = "" ，你可以执行 任意次 下述操作将 t 转换为 s ：
- 将字符串
"abc"插入到t中的任意位置。形式上，t变为tleft + "abc" + tright，其中t == tleft + tright。注意，tleft和tright可能为 空 。
如果字符串 s 有效，则返回 true；否则，返回 false。
示例 1：
输入：s = "aabcbc" 输出：true 解释： "" -> "abc" -> "aabcbc" 因此，"aabcbc" 有效。
示例 2：
输入：s = "abcabcababcc" 输出：true 解释： "" -> "abc" -> "abcabc" -> "abcabcabc" -> "abcabcababcc" 因此，"abcabcababcc" 有效。
示例 3：
输入：s = "abccba" 输出：false 解释：执行操作无法得到 "abccba" 。
提示：
1 <= s.length <= 2 * 104s由字母'a'、'b'和'c'组成