有效的括号
题目描述
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意： 空字符串可被认为是有效字符串。
示例 1:
输入: “()” 输出: true
示例 2:
输入: “()[]{}” 输出: true
示例 3:
输入: “(]” 输出: false
示例 4:
输入: “([)]” 输出: false
示例 5:
输入: “{[]}” 输出: true
题解
括号匹配是典型的代码分析问题，我们遍历字符串，每次处理一个括号，使用栈来保存这个括号。同时我们使用一个map来保存三种括号的开括号和闭括号。每次处理当前括号的时候，我们判断当前栈顶的元素是否是此括号对应的开括号，是的话，我们将弹出栈顶元素。否则我们将当前括号入栈。最后，如果栈的元素为空，那么可知此字符串是有效的字符串。
public boolean isValid(String s) {
if (s == null || s.length() == 0) {
return true;
}
Stack<Character> parenthesesStack = new Stack<>();
HashMap<Character, Character> parenthesesMap = new HashMap<>();
parenthesesMap.put('(', ')');
parenthesesMap.put('[', ']');
parenthesesMap.put('{', '}');
for (char parentheses : s.toCharArray()) {
if (!parenthesesStack.isEmpty() && Character.valueOf(parentheses)
.equals(parenthesesMap.get(parenthesesStack.peek()))) {
parenthesesStack.pop();
} else {
parenthesesStack.push(parentheses);
}
}
return parenthesesStack.isEmpty();
}复杂度分析
- 时间复杂度：O(n)，因为我们一次只遍历给定的字符串中的一个字符并在栈上进行 O(1) 的推入和弹出操作。
- 空间复杂度：O(n)，当我们将所有的开括号都推到栈上时以及在最糟糕的情况下，我们最终要把所有括号推到栈上。例如 ((((((((((。
来源
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-07-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
💥开发者 MCP广场重磅上线！
精选全网热门MCP server，让你的AI更好用 🚀
腾讯云开发者
