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

  • 2022-07-16 09:58:19

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

 

 使用动态规划

算法

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

This problem can be solved by using Dynamic Programming. We make use of a \text{dp}dp array where iith element of \text{dp}dp represents the length of the longest valid substring ending at iith index. We initialize the complete \text{dp}dp array with 0's. Now, it's obvious that the valid substrings must end with \text{‘)’}‘)’. This further leads to the conclusion that the substrings ending with \text{‘(’}‘(’ will always contain '0' at their corresponding \text{dp}dp indices. Thus, we update the \text{dp}dp array only when \text{‘)’}‘)’ is encountered.

To fill \text{dp}dp array we will check every two consecutive characters of the string and if

  1. \text{s}[i] = \text{‘)’}s[i]=‘)’ and \text{s}[i - 1] = \text{‘(’}s[i−1]=‘(’, i.e. string looks like ``.......()" \Rightarrow‘‘.......()"⇒

     

    \text{dp}[i]=\text{dp}[i-2]+2dp[i]=dp[i−2]+2

    We do so because the ending "()" portion is a valid substring anyhow and leads to an increment of 2 in the length of the just previous valid substring's length.

  2. \text{s}[i] = \text{‘)’}s[i]=‘)’ and \text{s}[i - 1] = \text{‘)’}s[i−1]=‘)’, i.e. string looks like ``.......))" \Rightarrow‘‘.......))"⇒

    if \text{s}[i - \text{dp}[i - 1] - 1] = \text{‘(’}s[i−dp[i−1]−1]=‘(’ then

     

    \text{dp}[i]=\text{dp}[i-1]+\text{dp}[i-\text{dp}[i-1]-2]+2dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2

The reason behind this is that if the 2nd last \text{‘)’}‘)’ was a part of a valid substring (say sub_ssubs​), for the last \text{‘)’}‘)’ to be a part of a larger substring, there must be a corresponding starting \text{‘(’}‘(’ which lies before the valid substring of which the 2nd last \text{‘)’}‘)’ is a part (i.e. before sub_ssubs​). Thus, if the character before sub_ssubs​ happens to be \text{‘(’}‘(’, we update the \text{dp}[i]dp[i] as an addition of 22 in the length of sub_ssubs​ which is \text{dp}[i-1]dp[i−1]. To this, we also add the length of the valid substring just before the term "(,sub_s,)" , i.e. \text{dp}[i-\text{dp}[i-1]-2]dp[i−dp[i−1]−2].

For better understanding of this method, see this example:

 

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

 

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

 

 

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;
    }
}

 

猜你喜欢