Longest Valid Parentheses
Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
(https://leetcode.com/problems/longest-valid-parentheses/description/)
动态规划算法
设dp[i] 为以s[i-1]为结尾的最长合法子串的长度,那么初始时,dp数组所有的元素都是0。
0 | 1 | 2 | … | i | … | n |
---|---|---|---|---|---|---|
S[0] | s[1] | s[2] | … | s[i] | … | s[n] |
dp[1]=0 | dp[2]=0 | dp[3]=0 | … | dp[i+1]=0 | … | dp[n+1]=0 |
我们计算dp[i]时,取得s[i-1],根据s[i]的值,分情况讨论:
- 如果 s[i-1] == ‘(’
由于以s[i]为结尾的子串是不合法的,所以dp[i]的值为0; - 如果 s[i-1] == ‘)’
则我们要跳过以s[i-1]结尾的最长合法子串s[j-1…i-1],长度也就是dp[i-1],j 的取值等于i - 1 - dp[i-1] - 1;然后查看s[j]字符。如果s[j]=’(’(j>0),该字符与s[i-1] 匹配,则dp[i] = dp[j] + 2 + dp[i-1]。如果 (j< 0) 或者s[j] = ‘)’,则没有以s[i-1] 为结尾的合法子串,dp[s] = 0。
1 | class Solution { |