力扣20. 有效的括号
一、题目描述：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"输出：true示例 2：
输入：s = "()[]{}"输出：true示例 3：
输入：s = "(]"输出：false示例 4：
输入：s = "([)]"输出：false示例 5：
输入：s = "{[]}"输出：true
提示：
1 <= s.length <= 10^4s 仅由括号 '()[]{}' 组成
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/valid-parentheses著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、思路分析：
这道题考察了什么思想？你的思路是什么？
- 我认为这道题目是简单的栈的使用，但是好久没用栈，都生疏了。因为我们每次遇到一个左括号，都入栈，然后遇到相同类型的右括号就出栈。因为后来的左括号需要相应的右括号先来，所以我们将后来的左括号放入栈顶。
做题的时候是不是一次通过的，遇到了什么问题，需要注意什么细节？
- 不是，第一次编写的代码如下，出现了问题，提交报错“Line 23: Char 17: runtime error: index -128 out of bounds for type 'char [*]' [solution.c]”。
charHashMap(charch){
if(ch=='}') return'{';
if(ch==')') return'(';
if(ch==']') return'[';
return0;
}
boolisValid(char*s){
intn=strlen(s);
if(n%2==1){
returnfalse;
}
chartemp[n+1],top=0;
for(inti=0;i<n;i++){
if(HashMap(s[i]) !=0){
if(top==0||temp[top-1] !=HashMap(s[i])){
returnfalse;
}
top--;
}
else{
temp[top++] =s[i];
}
}
if(top==0){
returntrue;
}else{
returnfalse;
}
}
- 但是我在本地Clion中输入那个测试用例又可以运行，真是头疼，于是我开始仔细阅读代码，终于发现了一个地方有问题。
chartemp[n+1],top=0;
- top应该是int类型，于是一改。。。
果然通过了。。。。
有几种解法，哪种解法时间复杂度最低，哪种解法空间复杂度最低，最优解法是什么？其他人的题解是什么，谁的效率更好一些？用不同语言实现的话，哪个语言速度最快？
- 本身是Python选手，看到了大佬写的Python解法，我自愧不如。
classSolution:
defisValid(self, s: str) ->bool:
dic = {'{': '}', '[': ']', '(': ')', '?': '?'}
stack = ['?']
forcins:
ifcindic: stack.append(c)
elifdic[stack.pop()] != c: returnFalse
returnlen(stack) == 1
作者：jyd
链接：https://leetcode-cn.com/problems/valid-parentheses/solution/valid-parentheses-fu-zhu-zhan-fa-by-jin407891080/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 这代码如此Pythonic。
三、AC 代码：
charHashMap(charch){
if(ch=='}') return'{';
if(ch==')') return'(';
if(ch==']') return'[';
return0;
}
boolisValid(char*s){
intn=strlen(s);
if(n%2==1){
returnfalse;
}
chartemp[n+1];
inttop=0;
for(inti=0;i<n;i++){
if(HashMap(s[i])){
if(top==0||temp[top-1] !=HashMap(s[i])){
returnfalse;
}
top--;
}
else{
temp[top] =s[i];
top++;
}
}
if(top==0){
returntrue;
}else{
returnfalse;
}
}
四、总结：
如果学栈的相关知识，这道题目应该是入门必做的！
