题目描述和要求
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例解释
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例 3：
输入：s = “(]”
输出：false
解题思路
可以使用栈来解决这个问题。遍历字符串，遇到左括号则入栈，遇到右括号则出栈。如果当前右括号与栈顶的左括号不匹配，则字符串无效。最后，如果栈为空，则字符串有效，否则无效。
算法实现
import java.util.Stack; public class ValidParentheses { public boolean isValid(String s) { if (s == null || s.length() == 0) { return true; } Stack<Character> stack = new Stack<>(); for (char c : s.toCharArray()) { if (c == '(' || c == '[' || c == '{') { stack.push(c); } else { if (stack.isEmpty()) { return false; } char top = stack.pop(); if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) { return false; } } } return stack.isEmpty(); } }
复杂度分析
- 时间复杂度：O(n)，其中 n 为字符串 s 的长度。遍历一次字符串。
- 空间复杂度：O(n)，最坏情况下栈的空间复杂度为 O(n)。
测试和验证
编写测试用例对算法进行验证，确保其正确性和健壮性。
public class Main { public static void main(String[] args) { ValidParentheses validParentheses = new ValidParentheses(); String s1 = "()"; System.out.println(validParentheses.isValid(s1)); // true String s2 = "()[]{}"; System.out.println(validParentheses.isValid(s2)); // true String s3 = "(]"; System.out.println(validParentheses.isValid(s3)); // false } }
总结和拓展
本题通过使用栈来判断字符串中的括号是否有效，实现了对字符串有效性的判断。这个算法思路清晰简单，在处理类似问题时是一个不错的选择。
除了当前算法，我们也可以考虑其他实现方式，例如使用递归、正则表达式等方法来解决类似问题。
参考资料
- 《力扣经典150题》
- LeetCode 官方网站
