Python中的最长括号匹配问题是给定一个只包含左括号'('和右括号')'的字符串,请设计算法找出其中最长的匹配子串
发布时间
阅读量:
阅读量
最长括号匹配 示例:
对于一个仅由左括号‘(’和右括号‘)’组成的字符串,可能存在括号不匹配的情况,需设计一种算法,以确定其中最长的匹配括号子串。
算法分析
仅当右括号与左括号成功配对时,才具备更新最终结果的可能性。
在计算s[0…i]区间内左括号与右括号的数量差值x时,若该差值为零,则需判断是否可以更新当前最优解。
这一差值x在代码中被定义为“深度”deep,并作为入栈的数据。
考虑到可能出现左括号数量多于右括号的情况,因此还需从字符串的右侧向左侧进行一次扫描操作。
利用deep值替代传统的栈结构,可将空间复杂度由O(N)优化至O(1)。
Python代码如下:
def match_longest_parentheses(s):
size = len(s)
li = [] # 记录最长结果的字符串索引,例如:对于"()(()"则返回[[0, 1], [3, 4]]
deep = 0 # 遇到多少左括号
start = 0 # 最深的(deep=0 时)左括号的位置
for i in range(size):
if s[i] == '(':
deep += 1
el
全部评论 (0)
还没有任何评论哟~
