leetcode-20.有效的括号

题意

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:

　输入: "{[]}"
　输出: true

算法

栈机制：遍历字符串，遇到左括号压栈，遇到右括号判断：若有与之匹配的左括号，弹栈，若不匹配，直接返回false
遍历完字符串，判断栈空，若空，返回true；否则，返回false

code

 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         //栈机制：遍历字符串，遇到左括号压栈，遇到右括号判断：若有与之匹配的左括号，弹栈，若不匹配，直接返回false
 5         //遍历完字符串，判断栈空，若空，返回true；否则，返回false
 6         vector<char> str;
 7         for(int i=0; i<s.size(); i++)
 8         {
 9             if(s[i] == '(' || s[i] == '[' || s[i] == '{')
10             {
11                 str.push_back(s[i]);
12             }
13             else if(s[i] == ')')
14             {
15                 if(str.empty())
16                     return false;
17                 if(str.back() == '(')
18                 {
19                     str.pop_back();
20                 }
21                 else
22                 {
23                     return false;
24                 }
25             }
26             else if(s[i] == ']')
27             {
28                 if(str.empty())
29                     return false;                
30                 if(str.back() == '[')
31                 {
32                     str.pop_back();
33                 }
34                 else
35                 {
36                     return false;
37                 }
38             }
39             else if(s[i] == '}')
40             {
41                 if(str.empty())
42                     return false;
43                 if(str.back() == '{')
44                 {
45                     str.pop_back();
46                 }
47                 else
48                 {
49                     return false;
50                 }
51             }
52         }
53         return str.empty();
54     }
55 };

上面代码，可读性太差，不够精简，重写了一下。

思路：map + stack机制，map存储括号的映射（注意是右括号映射左括号，因为后面要用右搜索左），stack做左括号的压栈弹栈操作。遇到右括号，如果栈空或者栈顶不是对应左括号（用map去找），返回false，否则，弹栈。

 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         int len = s.length();
 5         if(len == 0)
 6             return true;
 7         map<char, char> mp;
 8         mp[')'] = '(';
 9         mp[']'] = '[';
10         mp['}'] = '{';
11         stack<char> st;
12         for(char c : s)
13         {
14             if(c == '(' || c == '[' || c == '{')
15                 st.push(c);
16             else
17             {
18                 if(st.empty() || mp[c] != st.top())
19                     return false;
20                 else
21                     st.pop();
22             }
23         }
24         return st.empty();
25     }
26 };