首页 > 代码库 > [leetcode]Longest Valid Parentheses

[leetcode]Longest Valid Parentheses

2024-07-15 09:43:42   220人阅读

Longest Valid Parentheses

Given a string containing just the characters ‘(‘ and ‘)‘, find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

算法:

思路1 ：dp，感觉这道题略坑爹啊，还是屡一下思路吧，毕竟对DP完全不熟悉。

维护一个s.length()一维数组，dp，其中dp[i]表示从索引i到末尾所组成字符串的前缀最长的有效括号组合的长度。

例如：)()，则为0，而非2；())()，为2，表示的是前面的()

因此：dp[s.length() - 1] = 0;从后向前逆向求解dp[i]，

  1. 如果s[i]=‘)‘，则显然dp[i]=0;（均不合法）
  2. 如果s[i]=‘(‘，跳过dp[i+1]这段长度从j=i+1+dp[i+1]开始（找到最长前缀的后驱），如果j没越界并且s[j]=‘)‘，正好和s[i]匹配（组成了dp[i]的合法最长前缀），则dp[i]=dp[i+1]+2；另外此时可能j之后的也可以连上，所以，可能要加上dp[j+1];

代码如下：

 1 public class Solution { 2     public int longestValidParentheses(String s) { 3         if(s == null || s.length() < 2) return 0; 4         int max = 0; 5         int[] dp = new int[s.length()]; 6         dp[s.length() - 1] = 0; 7         for(int i = s.length() - 2; i >= 0; i--){ 8             if(s.charAt(i) == ‘(‘){ 9                 int j = i + 1 + dp[i + 1];10                 if(j < s.length() && s.charAt(j) == ‘)‘){11                     dp[i] = dp[i + 1] + 2;12                 if(j + 1 < s.length()){13                     dp[i] += dp[j + 1];14                 }15                 }16             }17             max = Math.max(max,dp[i]);18         }19         return max;20     }21 }
View Code

 

思路2： 这个思路有点吊，算法具体思想是，先把所有匹配的括号对，变成一样的标记，比如‘0’，例如：)()()()(()变成)000000(00，这样再求是不是容易多了？

代码如下：

 1 public class Solution { 2     public int longestValidParentheses(String s) { 3         if(s == null || s.length() < 2) return 0; 4         char[] charArray = s.toCharArray(); 5         for(int i = 0; i < s.length(); i++){ 6             char c = charArray[i]; 7             if(c == ‘)‘){ 8                 for(int j = i - 1; j >= 0; j--){ 9                     if(charArray[j] == ‘0‘) continue;10                     if(charArray[j] == ‘(‘){11                         charArray[i] = charArray[j] = ‘0‘;12                     }13                         break;14                 }15             }16         }17         int max = 0;18         for(int i = 0; i < s.length(); i++){19             if(charArray[i] == ‘0‘){20                 int begin = i;21                 while(i < charArray.length && charArray[i] == ‘0‘) i++;22                 max = Math.max(max,i - begin);23             }24         }25         return max;26     }27 }

 


联系
我们