2021 年 9 月 5 日 链接:https://leetcode-cn.com/problems/valid-parentheses/
题目
描述
给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例
示例 1:
输入:s = “()”
输出:true
示例 2:
输入:s = “()[]{}”
输出:true
示例 3:
输入:s = “(]”
输出:false
示例 4:
输入:s = “([)]”
输出:false
限制
- 1 <= s.length <= 104
-
解答
思路
创建栈
- 设置 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])){
} else {stack.push(s[i])
} } return stack.length === 0 };currentChat = stack.pop() if(currentChat !== chatMap[s[i]]){ return false }
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 = {
'}': '{',
')': '(',
']': '['
}