有效的括号

问题：

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

• 有效字符串需满足：

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

• 示例：

  1. 示例 1：
     输入：s = “()”
     输出：true
  2. 示例 2：
     输入：s = “()[]{}”
     输出：true
  3. 示例 3：
     输入：s = “(]”
     输出：false
  4. 示例 4：
     输入：s = “([)]”
     输出：false
  5. 示例 5：
     输入：s = “{[]}”
     输出：true

• 来源

  来源：力扣（LeetCode）
  链接：https://leetcode.cn/problems/valid-parentheses

分析问题

1. 括号是成对存在的，有2n个，字符串长度为偶数
2. 右括号前边一定跟着左括号，并且括号是互相匹配的，具有对称性

解法一：暴力消除

// 思路：因为 "()"、"[]" 都是成对存在的，那么可以将他们成对消除。例如 "{[()]}" 可以先消除 "()" 剩下 "{[]}" 依次类推，如果最终只剩下空字符串，则说明是有效的括号
// 代码实现
const isValid1 = (str) => {
    while(true) {
        len = str.length
        str = str.replace('()', '').replace('[]', '').replace('{}', '')

        // 当str.length = len时说明已经不能做替换了，此时如果len = 0则证明已经将全部的括号替换，此时为有效的括号，反之则为无效的括号
        if(str.length === len){
            return len === 0
        }
    }
}

解法二：栈方法

// 思路：因为括号是成对存在的，并且栈的特点就是"先进后出"。所以可以在每次入栈的时候，将入栈元素与栈顶元素对比，如果匹配，则清除对应元素，例如 "{[()]}"
// "{"入栈后栈内元素为[ "{" ]
// "["入栈后栈内元素为[ "{", "[" ]
// "("入栈，匹配到栈内元素 [ "{", "[", "(" ]
// ")"入栈时匹配到栈顶元素"(", "("出栈，此时栈内元素为 [ "{", "[" ]
// 以此类推，如果最终栈为空则为有效括号。
// 代码实现
 const isValid2 = (str) => {
    const strArr = str.split('')
    var arr = []  // 设置的栈
    // 匹配模式，注意是右括号匹配左括号，因为正常逻辑是先有左括号再有右括号
    const matching = {
        ')': '(',
        ']': '[',
        '}': '{'
    }

    strArr.forEach((item) => {
        // 当栈为空时，让第一个元素先入栈
        if(arr.length === 0) return arr.push(item)
        // 将要入栈的元素和栈顶元素对比，看是否匹配，如果匹配则栈顶元素出栈
        if(matching[item] === arr[arr.length - 1]){
            return arr.pop()
        }else {
            return arr.push(item)
        }
    })
    // console.log(arr)
    // 如果栈为空，则证明为有效括号
    if(!arr.length) return true
    return false
 }