Java O(n^2) dynamic programming solution


  • 0
    R

    I used a 2d array dp[index][count]. index represents the index of the parenthesis string. count represents the open/close count, where we add one for ( and subtract for ).

    The base case is dp[s.length()][0], which means that after we have check all of the previous characters and reach the end of the string, if the open count is 0, then that means we have found a valid parenthesis string.

    Now we iterate from the end of the string to the beginning, and calculate if index i can be a valid parenthesis at a every count j. We look at three cases:

    1. If the character at i is (, then we know we must increment our count by 1, so we see if dp[i + 1][j + 1] is valid.

    2. If the character is ), we will decrement our count by 1, so we see if dp[i + 1][j - 1] is valid.

    3. If the character is *, now we need to check all 3 possibilities where the * could be (, ), or a blank character, which is represented by dp[i + 1][j + 1], dp[i + 1][j - 1], and dp[i + 1][j]. If either one of those is true, then we know * at index i can make a valid parenthesis at the given count j.

    The answer will be dp[0][0].

    class Solution {
        public boolean checkValidString(String s) {
            boolean[][] dp = new boolean[s.length() + 1][s.length() + 1];
            dp[s.length()][0] = true;
            
            for(int i = s.length() - 1; i >= 0; i--) { //index
                char c = s.charAt(i);
                for(int j = 0; j < s.length(); j++) {//count
                    if(c == '(') {
                        dp[i][j] = dp[i + 1][j + 1];
                    } else if(c == ')') {
                        dp[i][j] = (j == 0) ? false : dp[i + 1][j - 1];
                    } else {
                        boolean open = dp[i + 1][j + 1];
                        boolean close = (j == 0) ? false : dp[i + 1][j - 1];
                        boolean nothing = dp[i + 1][j];
                        dp[i][j] = close || open || nothing;
                    }
                }
            }
            
            return dp[0][0];
        }
    }
    

Log in to reply
 

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