20、有效的括号 | JS-栈的应用

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"
输出：true
示例 2：

输入：s = "()[]{}"
输出：true
示例 3：

输入：s = "(]"
输出：false
示例 4：

输入：s = "([)]"
输出：false
示例 5：

输入：s = "{[]}"
输出：true

题解：

可以用字典Map

 1 /**
 2  * @param {string} s
 3  * @return {boolean}
 4  */
 5 var isValid = function(s) {
 6     if(s.length % 2 ===1) return false;
 7     const stack = [];
 8     const map = new Map();
 9     map.set('(',')');
10     map.set('{','}');
11     map.set('[',']');
12     for(let i=0; i<s.length; i+=1){
13         const c = s[i];
14         if(map.has(c)) {
15             stack.push(c);
16         }else{
17             const t = stack[stack.length - 1];
18             if(map.get(t) === c) {
19                 stack.pop();
20             }else{
21                 return false;
22             }
23         }
24     }
25     return stack.length === 0;
26 };

 1 /**
 2  * @param {string} s
 3  * @return {boolean}
 4  */
 5 var isValid = function(s) {
 6     if (s.length % 2 ===1) { return false; } //如果是奇数说明一定不匹配
 7     const stack = [];
 8     for(let i=0;i<s.length;i++){
 9         const c = s[i];  //拿到字符
10         if(c ==='(' || c ==='{' || c === '[') {
11             stack.push(c);
12         } else {
13             const t = stack[stack.length -1]; //t拿到栈顶
14             if(
15                 (t === '(' && c === ')') ||
16                 (t === '{' && c === '}') ||
17                 (t === '[' && c === ']') 
18             ) {
19                 stack.pop();
20             } else {
21                 return false;
22             }
23         }
24     }
25     return stack.length === 0;
26 };