现有一字符串仅由 ‘(’,’)’,’{’,’}’,’[’,’]'六种括号组成。
若字符串满足以下条件之一,则为无效字符串:
①任一类型的左右括号数量不相等;
②存在未按正确顺序(先左后右)闭合的括号。
输出括号的最大嵌套深度,若字符串无效则输出0。
0≤字符串长度≤100000
输入描述:
一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]'的字符串
输出描述:
一个整数,最大的括号深度
示例1
输入
[]
输出
1
说明
有效字符串,最大嵌套深度为1
示例2
输入
([]{()})
输出
3
说明
有效字符串,最大嵌套深度为3
示例3
输入
(]
输出
0
说明
无效字符串,有两种类型的左右括号数量不相等
示例4
输入
([)]
输出 0
说明
无效字符串,存在未按正确顺序闭合的括号
示例5
输入
)(
输出
0
说明
无效字符串,存在未按正确顺序闭合的括号
这题比想象中的要麻烦,思路为先确定字符串是否是合法字符串,再计算深度。有没有大神指导一下一步到位的解法,感激不尽。 力扣上有类似的题,把两题组合起来就是这道题的解法:
有效的括号 https://leetcode.cn/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode-solution/
括号的最大嵌套深度 https://leetcode.cn/problems/maximum-nesting-depth-of-the-parentheses/
// 是否是有效滴字符串
let str = '([]{()})'
let arr = str.split('')
let rightMarkArr = [')',']','}']
let objMark = {
')':'(',
']':'[',
'}':'{'
}
function test() {
let isValid = valid(arr)
let deep = 0
let maxDeep = 0
if(!isValid){
return 0
}
for(let i of arr){
if(!rightMarkArr.includes(i)){
deep++
maxDeep = Math.max(deep,maxDeep)
}else {
deep--
}
}
return maxDeep
}
// 是否是合法的字符串
function valid (arr){
let leftArr = []
if(arr.length%2!==0 || arr.length<1){
return false
}
for(let i of arr){
if(rightMarkArr.includes(i)){
if(objMark[i]!==leftArr[leftArr.length-1]){
return false
}
leftArr.pop()
}else{
leftArr.push(i)
}
}
return !leftArr.length
}
console.log(test());