Advertisement

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)

还没有任何评论哟~