程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode Longest Valid Parentheses

LeetCode Longest Valid Parentheses

編輯:關於C++

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

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved