O(N) DP Solution with Comprehensive Explanations


  • 0

    For questions asking about min/max values, I would typically think about DP solution. In contrast, questions asking about "find all" will lead to a recursion solution.

    So, if we came up the idea to use DP to solve it, the focus point will be -- what are the sub-problems?

    Let's take an example,

           ( ) ( ( ) ( 
    index  0 1 2 3 4 5
    

    Let's say, if we are standing at index 3, index 3 is "(", so the substring ending at index 3 will never be a valid one, because a valid substring cannot be ended at an open parentheses.

    Say, if we are standing at index 4 this time, index 4 is ")", so it can be valid. Thus, we need to check if there are available left parentheses in order to make it valid.

    And this comes with two kinds of situations: there is an immediate "(" before the current ")"; there is not. For the first situation, we can image this:

                 |   current looking at this one
                 v
    ...... ( ) ( )
               ^
               |   there is an immediate left parenthesis
    

    We can visualize the second situation like this:

                 |   current looking at this one, left parenthesis is not immediately next to it
                 v
    ...... ( ( ) )
           ^
           |   this is the left parenthesis
    

    These should conclude all the situations we need to care about.

    Therefore, we need to consider how to construct the DP structure. We will be using an array, with the same length of the string, each position stores the length of valid substring of the substring ending at the position. If the substring ending at position x is invalid, array[x] = 0; if is valid, array[x] stores the max length of substring which makes it valid. Maybe a little bit confusing, let's take an example:

                 ( ) ( ( ) ( 
    array index  0 1 2 3 4 5
    array value  
    

    At index 0, we check the substring ending at index 0, which is "(". The value at dp[0] should be the length of valid substring ending at this position of string "(", which should be 0 in this case, because none of the substrings will be valid.

    At index 1, we check the substring ending at index 1, which is "( )". The value at dp[1] should be the length of valid substring ending at this position of string "( )", which should be 2 in this case, because the substring "( )" is a valid substring of string "( )".

    At index 2, we check the substring ending at index 2, which is "( ) (". The value at dp[2] should be the length of valid substring ending at this position of string "( ) (", which should be 0 in this case, because it has these substrings ending with it, and none of them is a valid one.

    ( ) (       ) (       (     ---> substring with the same end as substring " ( ) ("
    0 1 2       1 2       2    ---> index at the original string
    

    At index 3, we check the substring ending at index 3, which is "( ) ( (". The value at dp[3] should be the length of valid substring ending at this position of string "( ) ( (", which should be 0 in this case, because it has these substrings ending with it, and none of them is a valid one.

    ( ) ( (      ) ( (       ( (      (   ---> substring with the same end as substring " ( ) ( ("
    0 1 2 3      1 2 3       2 3      3 ---> index at the original string
    

    At index 4, we check the substring ending at index 4, which is "( ) ( ( )". The value at dp[4] should be the length of valid substring ending at this position of string "( ) ( ( )", which should be 2 in this case, because it has these substrings ending with it, and only one of them is a valid one, with a length of 2.

    ( ) ( ( )      ) ( ( )       ( ( )       ( )      )   ---> substring with the same end
    0 1 2 3 4      1 2 3 4       2 3 4       3 4      4   ---> index at the original string
                                            valid
    

    Keep doing this, until the end.

    We get, the max of the values is the result.

                 ( ) ( ( ) ( 
    array index  0 1 2 3 4 5
    array value  0 2 0 0 2 0 
    

    More complex examples:

                 ( ( ( ) ) )
    array index  0 1 2 3 4 5
    array value  0 0 0 2 4 6 
    
                 ( ) ( ) ( ) ( ( )
    array index  0 1 2 3 4 5 6 7 8
    array value  0 2 0 4 0 6 0 0 2
    

    You have to understand these in order to continue. Take a minute to think about it.

    Now we move onto details. Like we mentioned above, standing at the position of each character, we will face this decision tree:

                    if charAt(i) is '('
                     yes /    \ no    -->  which means charAt(i) is ')'
                        /      \
                dp[i] = 0    if charAt(i-1) is '('   --> check if there is an immediate '('
                                 yes /    \ no
                                    /      \
                                   /        \
                  dp[i] = dp[i-2] + 2    if charAt(i-dp[i-1]-1) is '('
                                                yes /    \ no
                                                   /      \
                                                  /        \
                dp[i] = dp[i-dp[i-1]-2] + dp[i-1] + 2      dp[i] = dp[i-1]
    

    I know you may have question about the last two levels, let's use examples to explain:

    1. The dp[i] = dp[i-2] + 2 leaf
    ( ) ( )
    0 1 2 3  index
    0 2 0 4  value
    

    dp[3] = 4 because there is an immediate (, so it added length of 2 in addition to dp[i-2], so dp[3] = dp[3-2] + 2 = dp[1] + 2 = 4

    1. The if charAt(i-dp[i-1]-1) is '(' condition and its childrens
    ... ) ( ( ) ) 
        2 3 4 5 6  index
        4 0 0 2 8  value
    

    We are at index 6, and there is not an immediate "(". At index 5, we know that it has valid substring with length 2 ended at this index because dp[5] = 2, which is the substring in bold: ( ( ) )

    So in order to find a left parenthesis for index 6, we need to look at the index before this, which is index (i - dp[i-1] -1) = 3
    If index 3 is "(", we need to add three parts to get dp[i]: the parenthese's length of 2, the length of the middle block (which is dp[i-1] = 2), and the length before (which is dp[2] = 4), so dp[i] = 2 + dp[i-1] + dp[i-dp[i-1]-2] = 8

    You should be understanding the decision tree so far. If this makes sense, you can easily understand the code.

    The problem asks for the largest value, we just need to maintain the max after each calculating each position in the array.

    The code follows:

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

  • 0
    Z

    For the last rightmost leaf, I guess it should be dp[i] = 0?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.