Conventional DP, time O(n^2), could optimize to O(n) space.


  • 0
    V

    recurrence idea: for mark all the possible number of net '(' as true for the first i characters. At the end, check if net zero "(" is possible. On the way, cases with negative number of net '(' (i.e., some ')' appears before its closing ')') are not considered or marked. So later combinations depending on negative number of net '('s will not be true.

    public boolean checkValidString(String s) {
            if (s.length() == 0) {
                return true;
            }
            boolean[][] mem = new boolean[s.length()][s.length() + 1];
            char first = s.charAt(0);
            if (first == '(') {
                mem[0][1] = true;
            } else if (first == ')') {
                return false;
            } else {
                mem[0][0] = true;
                mem[0][1] = true;
            }
            for (int i = 1; i < s.length(); i++) {
                char c = s.charAt(i);
                for (int j = i + 1; j >= 0; j--) {
                    if (c == ')') {
                        if (j <= i) {
                            mem[i][j] = mem[i - 1][j + 1];
                        }
                    } else if (c == '(') {
                        if (j > 0) {
                            mem[i][j] = mem[i - 1][j - 1];
                        }
                    } else {
                        mem[i][j] = (j <= i ? mem[i - 1][j + 1] : false) || (j > 0 ? mem[i - 1][j - 1] : false) || mem[i - 1][j];
                    }
                }
            }
            return mem[s.length() - 1][0];
        }
    
    

  • 0
    D

    I am sorry, but might you give more detail about this idea? Why j begin from i+1, what mem[i][j] means, and what net '(' means, such that kinds of things. Thank you so much~~(^_^)


  • 0
    V

    @donggua_fu
    Sorry for the confusion.

    "net left open parentheses" means unbalanced '('. For example, "(()" has one unbalanced '(' and "(((())))" has zero unbalanced '('.

    mem[i][j] represents if the prefix s[0:i] can have j unbalanced '('. For example, string "()" can have 1 unbalanced '(' when the '' is regarded as a '(' OR it can have 0 unbalanced '(' when the '*' is regarded as an empty string. It can also be regarded as -1 unbalanced '(', but we does not record it, so this case will not be considered in the future.

    The reason that j starts from i+1 is because the prefix s[0:i] can at most have i+1 unbalanced '('.


  • 0
    D

    @vonzcy Really thanks for your patient~~(^_^)


Log in to reply
 

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