11.给出一个仅包含字符’(‘,’)‘,’{‘,’}‘,’[‘和’]’,的字符串,判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭,“()“和”()[]{}“都是合法的括号序列,但”(]“和”([)]“不合法。
示例1
输入:”()[]{}”
返回值:true
示例2
输入:“[]”
返回值:true
具体做法:
step 1:创建辅助栈,遍历字符串。
step 2:每次遇到小括号的左括号、中括号的左括号、大括号的左括号,就将其对应的呦括号加入栈中,期待在后续遇到。
step 3:如果没有遇到左括号但是栈为空,说明直接遇到了右括号,不合法。
step 4:其他情况下,如果遇到右括号,刚好会与栈顶元素相同,弹出栈顶元素继续遍历。
step 5:理论上,只要括号是匹配的,栈中元素最后是为空的,因此检查栈是否为空即可最后判断是否合法。
import java.util.*;
public class Solution {
public boolean isValid (String s) {
//辅助栈
Stack<Character> st = new Stack<Character>();
//遍历字符串
for(int i = 0; i < s.length(); i++){
//遇到左小括号
if(s.charAt(i) == '(')
//期待遇到右小括号
st.push(')');
//遇到左中括号
else if(s.charAt(i) == '[')
//期待遇到右中括号
st.push(']');
//遇到左打括号
else if(s.charAt(i) == '{')
//期待遇到右打括号
st.push('}');
//必须有左括号的情况下才能遇到右括号
else if(st.isEmpty() || st.pop() != s.charAt(i))
return false;
}
//栈中是否还有元素
return st.isEmpty();
}
}
版权声明:本文为liu8490631原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。