【刷题第九天】20. 有效的括号

一、题目描述：

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

有效字符串需满足：

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

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

二、思路分析：

计算机数据结构与算法学习过程中的经典案例——判断括号的有效性，可以通过栈这一数据结构来实现。

给定字符串 s ，我们按照括号泛式类型可以划分为两类，左括号和右括号。当遍历到左括号时，需要找一个同类右括号保证左括号有效。同时越晚遍历到的左括号应当是越早闭合，因此左括号适合放入栈中，越晚出现的左括号距离栈顶越近。

当遍历到右括号时，需要一个同类左括号与其闭合，因此此时就可以取出栈顶中的元素。

• 如果栈不空且同类型，继续遍历字符串

• 如果栈不空，但是括号是不同类型，说明字符串无效，循环中断直接返回 false
  

• 如果栈空，说明字符串无效，循环中断直接返回 false
  

当所有的字符串遍历完毕后，还有一种失效情况，千万不要忽略：遍历完毕后栈非空，说明字符串中存在多余的左括号，因此当前字符串也是无效的，返回 false

为了简化代码，我们省去字符串的对应判断，提前预处理将字符串存储为 map 形式，键为右括号，值为左括号。

三、AC 代码：

var isValid = function(s) {    const n = s.length; // 字符串长度    const stackStr = []; // 使用数组模拟栈    const kuohao = new Map([ // 预存储右括号与左括号的对应关系        [')', '('],        [']', '['],        ['}', '{']    ]);
    for (let i = 0; i<n; i++) {        if (kuohao.has(s[i])) { // 满足则为右括号            if (stackStr.length && kuohao.get(s[i]) === stackStr[stackStr.length - 1]) { // 判断栈顶元素是否与当前右括号的对应                stackStr.pop()            }else {                return false            }        }else {            stackStr.push(s[i])        }    }    return !stackStr.length; // 判断遍历完成后是否空栈，处理多左括号情况};复制代码

四、总结：

计算机数据结构与算法的基础题目，虽然这个题目拿上来就会做，但还是从题解学习到了 map 的处理方法，提前预存储一下右括号与左括号的关系，省去了大片 if else 判断，代码的清爽度提高很多。

不得不所，题解考虑的真全面，map 处理思维配合函数化思想，厉害