做外贸都做哪些网站好免费,汕头网页网站制作,注册文化传媒公司流程和费用,石油大学网页设计与网站建设描述
现有一字符串 仅由 (, ), {, }, [, ]一共六种括号组成。若字符串满足以下条件之一#xff0c;则为无效字符串。
任意类型的左右括号数量不相等存在未按正确顺序(先左后右)闭合的括号#xff0c; 输出括号的最大嵌套深度#xff0c;若字符串无效则输出 0。 0 字符…描述
现有一字符串 仅由 (, ), {, }, [, ]一共六种括号组成。若字符串满足以下条件之一则为无效字符串。
任意类型的左右括号数量不相等存在未按正确顺序(先左后右)闭合的括号 输出括号的最大嵌套深度若字符串无效则输出 0。 0 字符串长度 100000
输入描述 一个只包括 (, ), {, }, [, ] 以一共6种字符的字符串。
输出描述 一个整数表示最大的括号深度。若字符串无效则输出 0
示例1 输入[] 输出1 说明该字符串有效且最大嵌套深度为 1 示例2 输入([]{()}) 输出3 说明该字符串有效且最大嵌套深度为 3 示例3 输入(] 输出0 说明该字符串无效 示例4 输入([)] 输出0 说明该字符串无效 示例5 输入)( 输出0 说明该字符串无效 解题思路
首先创建一个空栈stack用于存储遇到的左括号。初始化最大深度max_depth为0。遍历字符串s中的每个字符c 如果c是左括号(, [, {将其压入栈中并更新最大深度max_depth为当前栈的长度和已知最大深度之间的较大值。如果c是右括号), ], }则检查栈是否为空或者栈顶元素是否与当前右括号匹配。如果不匹配说明括号不匹配返回0。如果匹配将栈顶元素弹出。 遍历结束后如果栈为空说明所有括号都匹配返回最大深度max_depth否则说明有未匹配的括号返回0。
def max_depth(s):stack []max_depth 0for c in s:if c in ([{:stack.append(c)max_depth max(max_depth, len(stack))elif c in )]}:if not stack or (c ) and stack[-1] ! () or (c ] and stack[-1] ! [) or (c } and stack[-1] ! {):return 0stack.pop()return max_depth if not stack else 0# 测试示例
print(max_depth([])) # 输出1
print(max_depth(([]{()}))) # 输出3
print(max_depth((])) # 输出0
print(max_depth(([)])) # 输出0
print(max_depth()()) # 输出0
