网站建设和管理经验恋月wordpress
原题地址：. - 力扣（LeetCode）
题目描述
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([])"
输出：true
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
解题思路
- 输入检查：首先检查输入字符串是否为空或长度为零。如果是，则返回
true，表示有效。- 长度检查：如果字符串的长度小于等于 1 或者是奇数，直接返回
false，因为无法匹配成对的括号。- 使用栈：创建一个栈来存放左括号。遍历字符串中的每个字符：
- 如果当前字符是左括号
(、[或{，将其压入栈中。- 如果当前字符是右括号
)、]或}，则检查栈是否为空：
- 如果为空，说明没有左括号可以匹配，返回
false。- 如果不为空，弹出栈顶元素并检查它是否与当前右括号匹配。如果不匹配，返回
false。- 结束检查：遍历完成后，如果栈为空，说明所有的左括号都有对应的右括号，返回
true；否则返回false。
源码实现
class Solution {public boolean isValid(String s) {// 检查输入是否为空或长度为零if (s == null || s.length() == 0) {return true; // 空字符串被认为是有效的}// 检查长度是否小于等于1或为奇数if (s.length() <= 1 || s.length() % 2 != 0) {return false; // 不能成对匹配}// 创建一个栈来存放左括号Stack<Character> stack = new Stack<Character>();// 遍历字符串中的每个字符for (char c : s.toCharArray()) {// 如果是左括号，压入栈中if (c == '(' || c == '[' || c == '{') {stack.push(c);continue;}// 如果是右括号，检查栈是否为空if (stack.isEmpty()) {return false; // 没有对应的左括号}// 检查栈顶元素是否匹配if (c == ')' && stack.pop() != '(') {return false; // 不匹配} else if (c == ']' && stack.pop() != '[') {return false; // 不匹配} else if (c == '}' && stack.pop() != '{') {return false; // 不匹配}}// 如果栈为空，所有括号都匹配，返回true；否则返回falsereturn stack.isEmpty();}
}
复杂度分析
- 时间复杂度：O(n)，其中 n 是字符串的长度。我们只需遍历字符串一次，栈的入栈和出栈操作的时间复杂度为 O(1)。
- 空间复杂度：O(n)，在最坏的情况下，栈中可能会存放所有的左括号（例如字符串为 "((("），因此需要 O(n) 的空间。