博文中会简要介绍Leetcode P0032题目分析及解题思路。
“Longest Valid Parentheses”是一道比较经典的动态规划问题，考察核心是寻找最优子结构和递推表达式
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
这道题的核心思路在于，当我们知道当前是右括号时，如何知道以这个右括号为结尾的合法括号串的长度，如果我们知道每一个这样的合法串的长度，我们就能知道最长的合法串的长度是多少。
仔细思考不难得知，右括号如果想要匹配，总是匹配它左边离它最近的未匹配的左括号。于是可以得到以下递推式：
令i是当前遍历到的前缀串长度，则i-1是当前下标指针指向的位置。
if s[i-1] == ')' && s[i-2] == '(':
dp[i] = dp[i-2]+2;
在这种情况下我们知道，如果该右括号前面一个字符是左括号，根据匹配规则，这个右括号一定是匹配前面这个左括号，所以以s[i-1]结尾的合法串长度等于dp[i-2]+2
if s[i-1] == ')' && s[i-2] == ')' && dp[i-1] != 0
left = i-1-dp[i-1]-1;
if (s[left] == '(')
dp[i] = dp[i-1]+2+dp[left]
这种属于核心情况，相对比较难理解。
如果s[i-1]前面还是右括号，那么我们首先想知道的是前面这个右括号有没有匹配，若没有匹配，那么也轮不到s[i-1]匹配，所以若dp[i-1] == 0即意味着没有以s[i-2]为结尾的合法串，即s[i-2]无匹配，那么s[i-1]也不可能有匹配，则跳过。
若dp[i-1]大于0，那么s[i-1]有希望匹配，下面就看以s[i-2]为结尾的合法串的前面一个字符是不是左括号，根据规则如果是左括号s[i-1]一定和它匹配，不然s[i-1]就没有匹配。如下：
) ( ) ( ( ( ) ) ( ( ) ( ) ) )
|<------- dp[i-1] ------>| i-1
可以发现，我们关注的是s[i-1-dp[i-1]-1]的位置是不是左括号，像上图这样就是符合匹配要求，则可以匹配，那么dp[i]的长度至少等于dp[i-1]+2。
那么为什么我们还要再加上dp[i-1-dp[i-1]-1]呢？原因是，有可能这个左括号恰好连接着两个合法串，此时匹配了可以造成一个更长的合法串。于是我们就知道需要查看被匹配的左括号前是不是也是合法串，所以需要直接加上dp[i-1-dp[i-1]-1]。
以下是Java的题解代码实现。
class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0)
return 0;
char[] chars = s.toCharArray();
int[] dp = new int[chars.length+1];
dp[0] = 0;
int maxLen = 0;
for (int i1=2; i1<=chars.length; ++i1) {
if (chars[i1-1] == ')' && chars[i1-2] == '(') {
dp[i1] = dp[i1-2]+2;
}
else if (chars[i1-1] == ')' && chars[i1-2] == ')') {
if (dp[i1-1] == 0)
continue;
if ((i1-1)-dp[i1-1]-1 >= 0) {
if (chars[(i1-1)-dp[i1-1]-1] == '(') {
dp[i1] = dp[i1-1]+2+dp[i1-dp[i1-1]-2];
}
}
}
maxLen = Math.max(maxLen, dp[i1]);
}
return maxLen;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int longestValidParentheses(string s) {
if (s.length() == 0)
return 0;
vector<int> dp(s.length()+1, 0);
int max_len = 0;
for (int i1=2; i1<=s.length(); ++i1) {
if (s[i1-1] == ')' && s[i1-2] == '(')
dp[i1] = dp[i1-2]+2;
else if (s[i1-1] == ')' && s[i1-2] == ')') {
if (dp[i1-1] == 0)
continue;
int last_pos = (i1-1)-dp[i1-1]-1;
if (last_pos >= 0 && s[last_pos] == '(') {
dp[i1] = dp[i1-1]+2+dp[last_pos];
}
}
max_len = max(max_len, dp[i1]);
}
return max_len;
}
};