32. Longest Valid Parentheses,

题意： 找出一个只包含”(“和”)”的字符串中最长的有效子字符串的长度。有效的意思是指该子字符串中的括号都能正确匹配

思路：动态规划，dp[i]表示以s[i]结尾的字符串所能组成的合规的子字符串的最大长度显然,对于s[i]是左括号而言，dp[i]=0, 如果s[i]是右括号，j := index - 1 - dp[index-1] 计算出了以s[i-1]结尾的子字符串的起始的前一个位置，如果s[j]是左括号且j>=0, 说明dp[i] = dp[i-1]+2, 即加上了j和i这两个位置的字符，此时还需要考虑dp[j-1], 如果j-1>0，则dp[i]的最终结果还要加上dp[j-1],因为dp[j-1]可能也大于0

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        # 6 star, 还需多看
        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)

Go:

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
func longestValidParentheses(s string) int {
	length := len(s)
	dp := make([]int, length)
	for index:=1; index < length; index++ {
		if string(s[index]) == ")" {
			j := index - 1 - dp[index-1]
			if j >= 0 && string(s[j]) == "(" {
				dp[index] = dp[index-1] + 2
				if j - 1 >= 0 {
					dp[index] += dp[j-1]
				}

			}

		}
	}
	max := 0
	for _, i := range dp {
		if i > max {
			max = i
		}
	}
	return max

}