Longest Valid Parentheses leetcode java (求最长有效匹配括号子串的长度)-动态规划

女爷i 2023-06-21 12:27 9阅读 0赞

LeetCode : Longest Valid Parentheses leetcode java (求最长有效匹配括号子串的长度)

划重点： 这道题的动态规划，不太好理解。

有两种方法：

方法一： 从前至后，进行动态规划， 直观一点遍历字符串，for (int i = 0 ; i < len; i++)

方法二： 从后向前，进行动态规划, 直观一点遍历字符串，for (int i = len ; i >0; i--)

下面具体一 一加以分析：

方法一：

使用动态规划

**算法**

通过使用动态规划可以解决此问题。我们利用\{dp\}dp数组，其中  \{dp\}dp表示最长有效子串的长度，结尾为索引。我们初始化完成\\ \{dp\}dp数组为0。现在，很明显，有效的子字符串必须以结尾 '） '。这进一步得出结论，子字符串以\\文本'（' 始终在其对应的位置包含'0'  \{dp\}dp索引。因此，我们更新了  \{dp\}dp数组仅当 '）' 遇到'）'。

为了更好地理解此方法，请参见以下示例：

![20191212200851129.gif][]

public class Solution {
        public int longestValidParentheses(String s) {
            int maxans = 0;
            int dp[] = new int[s.length()];
            for (int i = 1; i < s.length(); i++) {
                if (s.charAt(i) == ')') {
                    if (s.charAt(i - 1) == '(') {
                        dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                    } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                        dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                    }
                    maxans = Math.max(maxans, dp[i]);
                }
            }
            return maxans;
        }
    }

\----------------------------------------------------------------------------------------------------------------------

方法二：

需用到辅助数组d\[s.length()\]，表示从当前字符开始，到字符串结尾的最长有效括号子串长度（当前字符需为有效括号子串的第一个字符）

解题思路：从字符串结尾往前处理，求辅助数组d\[\]

当前字符下标为index，若当前字符为左括号'('，判断index+1+d\[index+1\]位置的字符是否为右括号')'，若为右括号，则d\[index\] = d\[index+1\]+2，并且判断index+1+d\[index+1\]+1位置的元素是否存在，若存在，则d\[index\] += d\[index+1+d\[index+1\]+1\]（解决上述两个有效括号子串直接相邻的情况）

其中，index， dp结果的移动比较乱一会+1，一会+2。 简单的记忆是，索引index下标加1移动，结果dp的结果是以加2移动。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdtYXg1NDIxMjAwOA_size_16_color_FFFFFF_t_70][]

class Solution {
        public int longestValidParentheses(String s) {
            if(null == s) return 0;
    
            int len = s.length(), max = 0;
            int[] d = new int[len];
    
            for(int index = len-2; index >= 0; index--){
                int symIndex = index+1+d[index+1];
                if('(' == s.charAt(index) && symIndex < len && ')' == s.charAt(symIndex)){
                    d[index] = d[index+1]+2;
                    if(symIndex+1 < len){
                        d[index] += d[symIndex+1];
                    }
                }
    
                max = Math.max(max, d[index]);
            }
            return max;

[20191212200851129.gif]: https://img-blog.csdnimg.cn/20191212200851129.gif
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdtYXg1NDIxMjAwOA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019121612045262.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdtYXg1NDIxMjAwOA==,size_16,color_FFFFFF,t_70