[Leetcode]

/** * Index: 32 * Title: Longest Valid Parentheses * Author: ltree98 **/

题意是求最长合法字符串。 只要中间不中断即可。 比如： (())() 是合法的。

stack

通过栈来实现。 1. 先压入一个 -1，方便计算长度。 2. 从第一个字符开始，依次判断；如果当前的字符与栈顶字符可以构成合法括号对，就弹出栈顶字符，计算长度；否则压入栈。 3. 将最大值返回。

这个方法，关键之处就在于第一个压入的-1，通过这个可以计算出不中断合法串的长度。

class Solution { public: int longestValidParentheses(string s) { stack<int> stk; stk.push(-1); int maxLen=0; for(int i = 0; i < s.length(); i++) { int t = stk.top(); if(t != -1 && s[i] == ')' && s[t] == '(') { stk.pop(); maxLen = max(maxLen, i-stk.top()); } else stk.push(i); } return maxLen; } };

dp

第二种方法是用动态规划来解。 从后向前遍历字符串。

dp[i] = 第i个字符开始到最后的最长匹配字符串的长度。

i = len-1 -> 0 s[i] 匹配 s[i+1+dp[i+1]] => dp[i] = dp[i+1]+2+dp[i+1+dp[i+1]] s[i] 不匹配 s[i+1+dp[i+1]] => dp[i] = 0

class Solution { public: int longestValidParentheses(string s) { int n = s.length(); int dp[100001]; memset(dp, 0, sizeof(dp)); int maxLen = 0; for(int i = n-2; i >= 0; i--) { if(s[i] == '(') { int j = i+1 + dp[i+1]; if(j < n && s[j] == ')') { dp[i] = dp[i+1]+2; if(j + 1 < n) dp[i] += dp[j+1]; } } maxLen = max(dp[i], maxLen); } return maxLen; } };