今天做一道比较简单的题,我们做题的顺序是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();
}