题目主要信息:
- 给定一个只包含大中小左右括号的字符串,判断其中括号是否合法
- 大中小括号的数学顺序与合法无关,只需要每种左括号在右边有相应匹配的右括号即可,不可交叉匹配,应该是括号嵌套
举一反三:
学习完本题的思路你可以解决如下题目:
方法:栈(推荐使用)
知识点:栈
栈是一种仅支持在表尾进行插入和删除操作的线性表,这一端被称为栈顶,另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;元素出栈指的是从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
思路:
括号的匹配规则应该符合先进后出原理:最外层的括号即最早出现的左括号,也对应最晚出现的右括号,即先进后出,因此可以使用同样先进后出的栈:遇到左括号就将相应匹配的右括号加入栈中,后续如果是合法的,右括号来的顺序就是栈中弹出的顺序。
具体做法:
- step 1:创建辅助栈,遍历字符串。
- step 2:每次遇到小括号的左括号、中括号的左括号、大括号的左括号,就将其对应的呦括号加入栈中,期待在后续遇到。
- step 3:如果没有遇到左括号但是栈为空,说明直接遇到了右括号,不合法。
- step 4:其他情况下,如果遇到右括号,刚好会与栈顶元素相同,弹出栈顶元素继续遍历。
- step 5:理论上,只要括号是匹配的,栈中元素最后是为空的,因此检查栈是否为空即可最后判断是否合法。
图示:
Java实现代码:
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();
}
}
C++实现代码:
class Solution {
public:
bool isValid(string s) {
//辅助栈
stack<char> st;
//遍历字符串
for(int i = 0; i < s.length(); i++){
//遇到左小括号
if(s[i] == '(')
//期待遇到右小括号
st.push(')');
//遇到左中括号
else if(s[i] == '[')
//期待遇到右中括号
st.push(']');
//遇到左打括号
else if(s[i] == '{')
//期待遇到右打括号
st.push('}');
//必须有左括号的情况下才能遇到右括号
else if(st.empty())
return false;
//右括号匹配则弹出
else if(st.top() == s[i])
st.pop();
}
//栈中是否还有元素
return st.empty();
}
};
Python代码实现:
class Solution:
def isValid(self , s: str) -> bool:
#辅助栈
st = []
#遍历字符串
for i, char in enumerate(s):
#遇到左小括号
if char == '(':
#期待遇到右小括号
st.append(')')
#遇到左中括号
elif char == '[':
#期待遇到右中括号
st.append(']')
#遇到左打括号
elif char == '{':
#期待遇到右打括号
st.append('}')
#必须有左括号的情况下才能遇到右括号
elif(len(st) == 0):
return False
#右括号匹配则弹出
elif(st[-1] == char):
st.pop()
#栈中是否还有元素
return len(st) == 0
复杂度分析:
- 时间复杂度:,其中为字符串长度,遍历整个字符串
- 空间复杂度:,最坏情况下栈空间中记录整个字符串长度的右括号