LeetCode_32: Longest Valid Parentheses

# 引言

题目链接：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

}