算法力扣刷题 二十九【20. 有效的括号】

前言

栈和队列篇，继续。
记录 二十九【20. 有效的括号】

---

一、题目阅读

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true
1
2

示例 2：

输入：s = "()[]{}"
输出：true
1
2

示例 3：

输入：s = "(]"
输出：false
1
2

提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
1
2

---

二、尝试实现

思路

题目意思是看括号有没有成功配对，并且配对顺序由内层到外层合理。
（1）首先，如果string长度是奇数，肯定是false。
（2）双指针法试试：行不通。

示例一：s = " {,[,(,),],} "，从两端指或者从一半的地方指；
对于示例二：s = "()[]{}"，不成立，所以pass。
1
2

（3）只能从头遍历string s.

• 如果遇到左括号，压入栈里；
• 如果遇到右括号，取一个栈顶元素，看是否配对？用栈可以满足大括号套中括号套小括号，嵌套时候的顺序配对正确。

代码实现

class Solution {
public:
    bool isValid(string s) {
        if(s.size()%2 != 0){ //奇数，肯定不配对。
            return false;
        }
        stack<char> stack1;
        for(int i = 0;i < s.size();i++){
            if(s[i] == '(' || s[i] == '[' || s[i] == '{'){
                stack1.push(s[i]);
            }else if(s[i] == ')'){
                if(!stack1.empty() && stack1.top() == '('){ //补充添加stack1不为空，如果有括号先出现，访问了空栈。
                    stack1.pop();
                }else{
                    return false;
                }
            }else if(s[i] == ']'){
                if(!stack1.empty() && stack1.top() == '['){
                    stack1.pop();
                }else{
                    return false;
                }
                
            }else if(s[i] == '}'){
                if(!stack1.empty() && stack1.top() == '{'){
                    stack1.pop();
                }else{
                    return false;
                }
            }
        }

        if(stack1.empty()){ //整个for循环结束，成功配对，stack1中不应该有元素。
            return true;
        }else{
            return false;
        }
        

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

两处细节修正：

• 如果s只有左括号，也是不配对的；for循环判断不出，所以最后加if(stack1.empty())。成功配对后，stack1中肯定是空。
• 如果一上来就是右括号，只是if(stack1.top() == ‘{’)，出现 访问空栈；所以需要加if(!stack1.empty() && stack1.top() == ‘(’) ，是否为空的判断。

---

三、参考思路

参考思路链接

学习内容

• 栈在对称匹配类题目中作用很大。
• 先分析了三种不匹配的情况： 左括号多余；右括号多余；括号类型不匹配；
• 技巧：如果是s[i]左括号，不是把左括号本身放到栈里，而是把其对应的右括号放到栈里。当s[i]是右括号时：只需要看当前栈顶元素是不是相等。
  • 如果栈为空：说明右括号多余；
  • 如果栈顶不相等：说明嵌套的顺序不对；
  • 如果遍历结束，栈不为空：说明左括号多余。
  • 总结：这个思路一开始就把所有情况都囊括，无需在实现之后查漏补缺。
• 对比思路下来：发现把右括号放进去，代码更简练，而不是拿着右括号去找左括号。

代码实现

class Solution {
public:
    bool isValid(string s) {
        if(s.size()%2 != 0){ //奇数，肯定不配对。
            return false;
        }
        stack<char> stack1;
        for(int i = 0;i < s.size();i++){
            if(s[i] == '(')
                stack1.push(')');
            else if(s[i] == '[')
                stack1.push(']');
            else if(s[i] == '{')
                stack1.push('}');
            else if(stack1.empty() || stack1.top() != s[i]){
                return false;
            }
            else stack1.pop();//注意：这里还得有else
        }
         
        return stack1.empty();	

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

有几处写的很好：

• 这样for循环return false是一条语句。
• 最后不是if判断空，而是直接return stack1.empty();

---

总结

• 栈用来解决对称匹配问题。
• 把匹配方（右括号）放进去，而不是把自己（左括号）放进去。拿着匹配方（右括号）去找相不相等。

（欢迎指正，转载标明出处）