给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
示例: 输入: "()" 输出: true 输入: "()[]{}" 输出: true 输入: "(]" 输出: false 输入: "([)]" 输出: false 输入: "{[]}" 输出: true
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
该题使用的堆栈(stack)的知识。栈具有先进后出(FILO)的特点。堆栈具有栈顶和栈底之分。所谓入栈,就是将元素压入(push)堆栈;所谓出栈,就是将栈顶元素弹出(pop)堆栈。先入栈的一定后出栈,所以可以利用堆栈来检测符号是否正确配对。
var isValid = function (s) {
var rightSymbols = []
for (var i = 0; i < s.length; i++) {
if (s[i] == '(') {
rightSymbols.push(')')
} else if (s[i] == '{') {
rightSymbols.push('}')
} else if (s[i] == '[') {
rightSymbols.push(']')
} else if (rightSymbols.pop() != s[i]) {
return false
}
}
return !rightSymbols.length
}
- 有效括号字符串的长度,一定是偶数!
- 右括号前面,必须是相对应的左括号,才能抵消!
- 右括号前面,不是对应的左括号,那么该字符串,一定不是有效的括号!
var isValid = function (s) {
let stack = []
if (!s || s.length % 2) return false
for (let item of s) {
switch (item) {
case '{':
case '[':
case '(':
stack.push(item)
break
case '}':
if (stack.pop() !== '{') return false
break
case '[':
if (stack.pop() !== ']') return false
break
case '(':
if (stack.pop() !== ')') return false
break
}
}
return !stack.length
}