我用JS刷LeetCode | Day 5 | Valid Parentheses
说明:现阶段的解题暂未考虑复杂度问题
首发地址:http://www.brandhuang.com/article/1583660931568
Given a string containing just the characters '(', ')', '{', '}', '[' and ']'
, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
给定一个只包括 '(',')','{','}','[',']'
的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
注意:
空字符串可被认为是有效字符串。
Example:
Input: "()"
Output: true
Input: "()[]{}"
Output: true
Input: "(]"
Output: false
Input: "([)]"
Output: false
Input: "{[]}"
Output: true
- 由题目「
空字符串可被认为是有效字符串
」, 当输入空字符串时,返回true
。 - 声明一个对象
(Obj)
,用对象的 key 和 value 值来保存这成对出现的括号,要满足题目中「有效的字符串」
,必定是以左括号开始,右括号闭合
,所以我们用Obj
的key
来存左括号,key
对应的value
值来存右括号。 - 遍历输入的字符串,声明一个数组
(arr)
,来存放遍历出的和Obj
中的key
相等的字符。 - 如果遍历出的元素
不是 Obj 中的 key
,说名此元素必定是一个右括号
。 - 取出第 3 步中存入数组中的字符,如果从数组中取出的值在
Obj
中对应的value
和第 4 步遍历出的元素相同
,则说明是一个有效的字符
,否则这个右括号
没有对应的左括号
,是一个无效的字符串
, 此时返回false
。 - 如果在遍历完输入的字符串后,第 3 步中的数组为空,则说明输入的字符串刚好都是
有效的字符串
,否则是无效字符串
。 - 得出如下答案。
var isValid = function (s) {
if (!s) return true
let obj = {
'(': ')',
'{': '}',
'[': ']',
}
let arr = []
for (let i = 0; i < s.length; i++) {
if (s[i] in obj) {
arr.push(s[i])
} else {
var current = arr.pop()
if (obj[current] !== s[i]) {
return false
}
}
}
return arr.length === 0
};
本题更多 JavaScript
解析,点击链接访问对应的答案:https://leetcode.com