- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
栈
先明确题意，所谓“有效的括号”，不仅要保证左括号的数量和右括号的数量相等，还要保证括号的位置。
显然，有效括号的部分子表达式中也是有效的括号。
我们可以借助栈来解题，栈满足后进先出，这样在遍历的过程中，每次与栈顶的元素相匹配，能够保证是最近出现的元素。
- 排除掉奇数个括号或是右括号开头的情况。
- 如果是
'(' 、'{'、'['等左括号则直接入栈。 - 否则就是右括号，将其与栈顶元素匹配，匹配失败则是无效的括号返回 false，成功则继续遍历。
- 当遍历完成时，栈如果为空则是有效的括号返回 true，若栈不为空则意味着还有无法匹配的括号，返回 false。
constisValid=function(s){// 奇数个括号或右括号开头的情况无效if(s.length%2!==0||[')',']','}'].indexOf(s[0])!==-1)returnfalseconstmap={'(':')','[':']','{':'}'}conststack=[]for(leti=0;i<s.length;i++){if(s[i]==='('||s[i]==='{'||s[i]==='['){stack.push(s[i])}elseif(s[i]!==map[stack.pop()]){returnfalse}}returnstack.length===0}
- 时间复杂度: O(n)
- 空间复杂度: O(n)