# 引言

题目链接:https://leetcode.com/problems/longest-valid-parentheses/

# 题目大意

给定一个只包含字符 '(' 和 ')' 的字符串,找到最长的有效 (括号配对) 括号子字符串的长度。

  • Example
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

# 题解

明确一个要点,一个匹配的字符串一定是以 ')' 结尾

假设 dp[i] 表示从字符串开头以第 i 位结尾的子字符串的最大匹配长度,每次读取到为 ')' 的字符串只需要判断第 i-1-dp[i-1] 对应索引是否为 '(' 即可

于是有如下状态转移方程

dp[i] = dp[i-1] + 2 ( s[i] == ')' && s[i-1-dp[i-1]]=='(' )
dp[i] += dp[i - dp[i]];

递归边界dp[0] = 0

再进行 dp 时注意维护最大值即可,为了避免越界情况,博主采取在目标字符串头部添加一个无效字符。

# 复杂度

时间复杂度 O(n)

空间复杂度 O(n)

# AC 代码

c++ 版本

class Solution
{
  public:
    int longestValidParentheses(string s)
    {
        int ans = 0;
        string prefixs = "#" + s;
        vector<int> dp(prefixs.length(), 0);
        for (int i = 1; i < prefixs.length(); ++i)
        {
            // 更新
            if (prefixs[i] == ')')
            {
                if (prefixs[i - dp[i - 1] - 1] == '(')
                {
                    dp[i] = dp[i - 1] + 2;
                }
                dp[i] += dp[i - dp[i]];
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

go 版本

func longestValidParentheses(s string) int {
	prefixs := strings.Join([]string{"#", s}, "")
	ans, lens, dp := 0, len(prefixs), make([]int, len(prefixs))
	for i := 1; i < lens; i++ {
		if prefixs[i] == ')' {
			if prefixs[i-1-dp[i-1]] == '(' {
				dp[i] = dp[i-1] + 2
			}
			dp[i] += dp[i-dp[i]]
		}
		if ans < dp[i] {
			ans = dp[i]
		}
	}
	return ans
}
更新于 阅读次数

请我喝[茶]~( ̄▽ ̄)~*

yx.zhang 微信支付

微信支付

yx.zhang 支付宝

支付宝