面试官：数据结构了解多少？来看看这道题！

前言

在面试题当中，数据结构考察还是比较多的，特别是面试考察算法的时候，它会成为你进入大厂时越过的必不可少的沟壑。

话不多说，上题目！

有效的括号

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

有效字符串需满足：

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

示例

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

思路分析

首先做题，我们就需要从示例当中找出规律。

• 1、观察数组长度，我们可以发现，如果匹配成功，字符串长度必须是偶数，奇数长度无法匹配成功
• 2、按照括号匹配规则，右括号一定出现在左括号右边
• 3、如果能够被消除成功，那么至少有一对匹配的括号是紧挨着的

初步行动

根据我们第三点的发现，无论哪种括号匹配成功的情况，至少有一对匹配的括号紧挨着。不知道大家是否玩过消消乐，如果整组图形能够被消除，那么必然会给你留一个‘三连图’，否则系统自动判断没有可以消除的，直接换一组图形，我们的括号匹配也类似于消消乐。

而我们的题目只有‘（）’‘[]’‘{}’这三种图形，无疑降低了难度。

我们先假设紧挨的一组括号为'()'

• 首先匹配'()',将其消除，替换为空字符串.
• 那么剩余的括号，可能消除之后是'[]'相连，'()'相连或者是'{}'相连
• 之后相继匹配'()''[]' 或者‘{}’,将其消除，替换为空字符串.
• 如果还有括号剩余，或者有一个步骤当中没有括号被消除，说明该字符串无法进行括号匹配，返回false

当然这需要循环调用，而我们需要注意循环条件，就是消除之后s长度的变化。

代码

const isValid = (s) =>{
  while (true) {
    let length = s.length 
// 将字符串按照匹配对，相继替换为'' 
    s = s.replace('{}', '')
    s = s.replace('[]', '')
    s = s.replace('()', '') 
// 当长度相等的时候两种状况，要么都为0,消除成功；要么括号没有消除，匹配失败
    if (s.length == length && length == 0) {
    return length == 0
    }
  } 
}

优化

前面的算法相当于是暴力循环，像每次循环可能有些操作是多余的，我们换种思路。

括号消除，可以说是配对消除的，我们将每个字符看做一个个体，将配对的括号看做一个有机整体，将其拆分为左括号，与右括号，类似于双方博弈，然后左右两边按照顺序相互抵消，但是左括号又要按照一个顺序来利用右括号抵消，没错，就是今天的主角--栈结构。

先进栈的左括号总是被最后消除，最后进入的左括号总是被最先消除，这就类似于我们的栈结构，先进后出。

• 首先需要定义相应的抵消规则，'(' 只能被')'抵消，以此类推
• 按照字符串顺序进栈，注意只能将左括号入栈，如果遇到右括号，那么就要将栈顶元素弹出，与其进行抵消
  • 该元素与栈顶元素相同，那么抵消成功，进行下一个字符串的情况
  • 该元素与栈顶元素不同，那么说明括号匹配失败，直接返回false
• 最后我们只需要看最终抵消的情况，如果栈仍然有元素剩余，说明没有相应的右括号，匹配失败

代码

const isValid = (s) =>{
    let st = []
    for (let i = 0; i < s.length; i++) {
            //只允许左括号入栈
            if (s[i] == '(')
             st.push(')');
            else if (s[i] == '{') 
            st.push('}');
            else if (s[i] == '[') 
            st.push(']');
            
            //此处为右括号的操作，右括号的处理情况
            // 遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
            // 遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
            else if (st.length == 0 || st[st.length - 1] !== s[i]) 
            return false;
            //检测栈是否为空或者栈顶元素是否与其相同
            else st.pop(); // 若是st.top() 与 s[i]相等，栈弹出元素
        }
        // 此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，
        //若是已经为空，则匹配成功，return true
        return st.length == 0;
}

在此处，我也有个小小的疑问，访问栈顶元素使用st.peek()的时候会报错，在浏览器使用也显示没有改方法，还请大佬解答一下。

总结

代码之路还是很长，数据结构仍然复杂，这只是比较简单的一道题目，但是对于一道简单的题目，我也希望能够展示不同的解法，但是有些题目毕竟脑子有限，想的头疼，就只弄出一种了，而弄出一种也不简单，算法题就是这样，算法虐我千百遍，我待算法如初恋，希望有一天能够我虐算法千百遍，算法待我如初恋吧！哈哈哈

我是小白，一名不折不扣的js拥护者菜鸟，我们一起学习！