介绍动态规划的解法
从倒数第二个元素往前遍历，特别针对 " ( ) " 的情况。用一维数组保存结果,d[i] 代表从当前下标 i 到字符串 s 最末尾的子串中的最长有效子串的长度。动态方程如何写呢？对于当前下标i，如果是 ' ( '，则考虑右边子串中的元素，是否为 ' )'。考虑哪一个呢？ symi 变量是怎么想到的呢？后来我思考发现，发现原作设置的 symi 变量确实巧妙。symi 代表对于当前下标i，需要进行匹配的右括号的位置。此时若是匹配，则得到的 d[i] 代表从 i 到 symi 之间的子串的最长有效子串长度，如果下标 symi 右边还有元素。则需要加上 d[symi+1]。 1 public class Solution { 2 public int longestValidParentheses(String s) { 3 if(null == s) return 0; 4 int len = s.length(), max = 0; 5 int[] d = new int[len]; 6 for (int i = len-2; i >= 0; i--){ 7 int symi = i+1+d[i+1]; 8 if ('(' == s.charAt(i) && symi < len && ')' == s.charAt(symi)){ 9 // 如果满足条件，则相当于在d[i+1]的基础上又多了一对"（）"，所以长度+2 10 d[i] = d[i+1]+2; 11 // 如果symi右边还有元素，那么d[i]就应该加上d[symi+1] 12 if(symi+1 < len){ 13 d[i] += d[symi+1]; 14 } 15 } 16 max = Math.max(max, d[i]); 17 } 18 return max; 19 } 20 }
转载于:https://www.cnblogs.com/dogeLife/p/11000444.html
