给定一个仅包含字符 '('
, ')'
, '{'
, '}'< 的字符串
、'['
和 ']'
,判断输入字符串是否有效。
输入字符串在以下情况下有效:
- 左括号必须用相同类型的括号封闭。
- 左括号必须按正确的顺序闭合。
- 请注意,空字符串也被视为有效。
示例1:
Input: "()[]{}"
Output: true
Example 2:
示例2:
Input: "{[(])}"
Output: false
针对上述问题我的解决方案是:
static boolean isPair(char left,char right){
return left=='{' && right=='}' || left=='(' && right==')' || left=='[' && right==']';
}
public boolean isValid(String s) {
Stack<Character> stack= new Stack<>();
for(char ch: s.toCharArray()){
if(ch=='(' || ch=='{' || ch=='['){
stack.push(ch);
}
else{
if(!stack.isEmpty() && isPair(stack.peek(),ch))
stack.pop();
else
return false;
}
}
return stack.isEmpty();
}
我在某处找到了一个更聪明的解决方案,但无法理解它。 代码如下:
public boolean isValid(String s) {
Stack<Character> stack= new Stack<>();
for(char ch: s.toCharArray()){
if(ch=='(')
stack.push(')');
else if(ch=='{')
stack.push('}');
else if(ch=='[')
stack.push(']');
else if(stack.isEmpty() || stack.pop()!=ch)
return false;
}
return stack.isEmpty();
}
请帮助我理解最后一个 else-if
block 的工作原理。
最佳答案
您已经为所有左括号
按下了右括号
。因此,当右括号出现时,它将匹配堆栈顶部的字符。如果不匹配或者堆栈变空。这意味着不平衡。
else if(stack.isEmpty() || stack.pop()!=ch)
return false;
当你到达这里时,你有一个括号
作为ch,但堆栈是空的或者堆栈中的值与传入的字符不匹配。
因此,括号不平衡。
关于java - 平衡括号问题的优化解,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57117715/