LeetCode 解题报告 (32)-- 最长合法的子括号串

发表于 标签 ， ，

原题如下：
>Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

>For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

题目的要求从给出的包含括号的 string 中找到最长的合法 string。

最暴力的方法就是从长到短遍历 string 中的所有可能的 subString，再判断 subString 是否合法，这种方法的时间复杂度是 \(O(n^3)\)，提交时 TLE。

两种比较巧妙的方法的方法的时间复杂度都是 O (n)，一种是动态规划，一种是利用栈存储不合法的括号的位置。

下面分别列出这三种方法

方法一，暴力枚举，时间复杂度 \(O(n^3)\)

虽然容易理解，答案也正确，但是提交超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution(object):  
    def longestValidParentheses(self, s):  
        """  
        :type s: str  
        :rtype: int  
        """  
        if len(s)<2:  
           return 0  
        left = 0  
        right = 0  
        for i in range(len(s)):  
            if s[i] == '(':  
                left+=1  
            elif s[i] == ')':  
                right+=1

        m = min(left,right)

        cut = len(s)-2*m # 从长到短遍历  
        while cut<=len(s)-2:  
            subLen = len(s) - cut  
            for i in range(cut+1):  
                subStr = s[i:i+subLen]  
                if subStr[0] == ')':  
                    continue  
                if self.isValid(subStr):  
                    return subLen  
            cut +=2  
    # 判断子字符串是否有效  
    def isValid(self,s):  
        stack = []  
        for i in range(len(s)):  
            if s[i] == '(':  
                stack.append('(')  
            elif s[i] == ')':  
                if len(stack)>0:  
                    stack.pop(len(stack)-1)  
                else:  
                    break

        if len(stack)==0 and i==len(s)-1:  
            return True  
        else:  
            return False

方法二，动态规划，时间复杂度 \(O(n)\)

DP 会先建立一个 longest 列表，其中 longest [i] 代表以 s [i] 结尾的最长合法串的长度。这样便有了以下判断条件：

  • 假如 s[i]=( ，那么 longest [i]=0
  • 假如 s[i]=) && s[i-1]=( , 那么 longest [i]=longest [i-2]+2
  • 假如 s[i]=) && s[i-1]=) && s[i-longest[i-1]-1]==( , 那么 longest [i]=longest [i-longest [i-1]-2]+longest [i-1]+2
  • 假如上面情况都不符合那么，longest [i] = 0

实现代码如下，提交时能够 AC：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):  
    def longestValidParentheses(self, s):  
        """  
        :type s: str  
        :rtype: int  
        """  
        longest = []  
        longest.append(0)  
        for i in range(1,len(s)):  
            if s[i] == '(':  
                longest.append(0)  
            else:  
                if i-1>=0 and s[i-1]=='(':  
                    longest.append(longest[i-2]+2)  
                elif i-1>=0 and s[i-1]==')' and i-longest[i-1]-1 >=0 and s[i-longest[i-1]-1]=='(':  
                    tmp = longest[i-longest[i-1]-2] if i-longest[i-1]-2>=0 else 0  
                    longest.append(longest[i-1]+2+tmp)  
                else:  
                    longest.append(0)  
        return max(longest)

方法三，通过栈存储不合法的括号位置，时间复杂度 \(O(n)\)

这种方法通过栈来存储不合法的括号的位置。

具体流程是先遍历字符串 s，遇到左括号就将位置其入栈，遇到右括号就检查栈顶是否有左括号号，有的话就弹出这个左括号，否则将右括号的位置入栈。最后得到的栈中的元素就是原来 str 中不合法的括号的位置，那么栈中相邻位置的元素的差值就是一个合法的括号串的长度，找到其中最大值即可。

需要注意的是最后遍历栈找最长合法串时需要在最左边和最右边分别加上 -1 和 len(s)(s 就是原字符串的长度)，目的是为了当原字符串最左边或最右边的括号均为合法时能够被计算长度。

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):  
    def longestValidParentheses(self, s):  
        """  
        :type s: str  
        :rtype: int  
        """  
        maxLen = 0  
        stack=[]  
        for i in range(len(s)):  
            if s[i] == ')' and len(stack)>0 and s[stack[-1]]=='(':  
                stack.pop(len(stack)-1)  
                maxLen = 2  
            else:  
                stack.append(i)


        # 全匹配  
        if len(stack) == 0:  
            return len(s)  
        # 不在不匹配的要在头尾插入元素来计算头或尾匹配的括号  
        stack.append(len(s))  
        stack.insert(0,-1)  
        j = len(stack)-1  
        while j>0:  
            maxLen = max(maxLen,stack[j]-stack[j-1]-1)  
            j -= 1  
        return maxLen

参考：
【1】https://leetcode.com/discuss/7609/my-o-n-solution-using-a-stack
【2】https://leetcode.com/discuss/8092/my-dp-o-n-solution-without-using-stack