LeetCode解題之Longest Valid Parentheses

原題

找出一個只包含”(“和”)”的字符串中最長的有效子字符串的長度。有效的意思是指該子字符串中的括號都能正確匹配。

注意點：

例子：

輸入: s = “(()”
輸出: 2

輸入: s = “)()())”
輸出: 4

解題思路

采用了動態規劃，dp[i]表示以i為子字符串末尾時的最大長度，最後的結果就是dp中的最大值。如果不是空字符串，則dp[0]=0，因為一個括號肯定無法正確匹配。遞推關系是:

) ( ) ( ( ) ) )
0 1 2 3 4 5 6 7

看當前括號的前一個括號的匹配情況，例如在7之前以6結尾的的最佳匹配是3-6，看3之前的括號和7是否匹配，不匹配則沒有變化；而6之前以5結尾的最佳匹配是4-5，此時3和6匹配，則dp[i]+2。此外，如果與當前括號匹配的左括號之前的括號的dp值也應該加進來，因為由於添加了當前的括號，那些括號也被連接起來了。例如3和6匹配後，1和2也應該被加到以6結尾的最佳匹配中。

AC源碼

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        length = len(s)
        dp = [0 for __ in range(length)]
        for i in range(1, length):
            if s[i] == ")":
                j = i - 1 - dp[i - 1]
                if j >= 0 and s[j] == "(":
                    dp[i] = dp[i - 1] + 2
                    if j - 1 >= 0:
                        dp[i] += dp[j - 1]
        return max(dp)


if __name__ == "__main__":
    assert Solution().longestValidParentheses("(()))())(") == 4
    assert Solution().longestValidParentheses("(()") == 2
    assert Solution().longestValidParentheses(")()())") == 4