2021 年 9 月 5 日 链接:https://leetcode-cn.com/problems/valid-parentheses/

题目

描述

给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例

示例 1:
输入:s = “()”
输出:true

示例 2:
输入:s = “()[]{}”
输出:true

示例 3:
输入:s = “(]”
输出:false

示例 4:
输入:s = “([)]”
输出:false

示例 5:
输入:s = “{[]}”
输出:true

限制

  • 1 <= s.length <= 104
  • s 仅由括号 ‘()[]{}’ 组成

    解答

    思路

  • 创建栈

  • 设置 chatMap,将右括号与左括号关联chatMap = {'}':'{',')':'(',']':'['}
  • 遍历字符串
    • 如果当前字符为左括号,传入栈
    • 如果当前字符为右括号,将栈中内容推出
    • 将栈中推出的内容与当前字符对比,如果不相同,则直接返回 false,因为出现括号嵌套的场景了 {[}]

      代码

      ```javascript /**
      • @param {string} s
      • @return {boolean} */ var isValid = function(s) { const stack = [] let currentChat = ‘’ for(let i = 0; i < s.length; i++){ if([‘{‘, ‘(‘, ‘[‘].includes(s[i])){
        1. stack.push(s[i])
        } else {
         currentChat = stack.pop()
         if(currentChat !== chatMap[s[i]]){
             return false
         }
        
        } } return stack.length === 0 };

const chatMap = { ‘}’: ‘{‘, ‘)’: ‘(‘, ‘]’: ‘[‘ }

<a name="NN6xk"></a>
### 思路2

- 可用字符串变量优化,减少空间复杂度
- 空间复杂度 0(1)
```javascript
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let newS = ''
    for(let i = 0; i < s.length; i++){
        if(['{', '(', '['].includes(s[i])){
            newS += s[i]
        }
        else if(chatMap[s[i]] !== newS[newS.length - 1]){
            return false
        }
        else{
            newS = newS.slice(0, -1)
        }
    }
    return newS.length === 0
};

const chatMap = {
    '}': '{',
    ')': '(',
    ']': '['
}