每日算法题——有效的括号
今天做一道比较简单的题，我们做题的顺序是leetcode的100道热题，从简单到难这么一个顺序
题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
示例1：
输入: "()"
输出: true
示例2：
输入: "()[]{}"
输出: true
示例3：
输入: "(]"
输出: false
示例4：
输入: "([)]"
输出: false
示例5：
输入: "{[]}"
输出: true
思路
这种括号匹配的题目不知道大家在面试过程中有没有遇到相似的，这里匹配的特性我们用栈来操作比较形象，想象一下，遍历整个字符串，将左括号入栈，遍历遇到右括号的话取栈顶元素与之匹配，如果不能匹配上，那说明这不是一个有效的括号，如果匹配上了，将栈顶元素出栈，然后就继续遍历，直到遍历结束，判断栈最后是不是空的，如果是空的，那就说明这是一个有效的字符串
代码
public static boolean isValid(String s) {
if (s.equals("")) {
return true;
}
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char character = s.charAt(i);
// 判断是左括号，入栈
if (character == '(' || character == '[' || character == '{') {
stack.push(character);
} else {
// 如果发现是右括号，但是栈中没有左括号
if (stack.empty()) {
return false;
}
// 判断栈中的左括号与当前的右括号是否匹配，匹配的话就将栈中的左括号出栈然后进行下一次匹配
if (character == ')' && stack.peek() == '('
|| character == ']' && stack.peek() == '['
|| character == '}' && stack.peek() == '{') {
stack.pop();
} else {
return false;
}
}
}
// 最后判断栈是否为空
return stack.empty();
}
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-02-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录