678. Valid Parenthesis String

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

1. Any left parenthesis'('must have a corresponding right parenthesis')'.

2. Any right parenthesis')'must have a corresponding left parenthesis'('.

3. Left parenthesis'('must go before the corresponding right parenthesis')'.

4. '*'could be treated as a single right parenthesis')'or a single left parenthesis'('or an empty string.

5. An empty string is also valid.

Example 1:

Input: "()"

Output: True

Example 2:

Input: "(*)"

Output: True

Example 3:

Input: "(*))"

Output: True

Thoughts:

1. DP

2. "two counter": min_op_left: how many open "(" if regarding all * to be ")"; max_op_left: how many open "(" if regarding all * to be "("

   1. key idea: max_op_left should always be >= 0 in order to be considered legal, otherwise it will have unbalanced ")" and the parenthesis will never be balanced by further appending any char after it.

Code: unordered DP with memoization Time: O(n^3) Space: O(n^2), Top-Down

class Solution {
public:
    bool checkValidString(string s) {
        int n = s.length();
        f = vector<vector<int>> (n, vector<int>(n, -1));
        return isValid(s, 0, n - 1);

    }
private:
    vector<vector<int>> f;
//  method checking substring s[start,...end] is valid
    bool isValid(const string &s, int start, int end){
        if(start > end) return true;
        if(start == end) return f[start][end] = (s[start] == '*');
        if(f[start][end]>= 0) return f[start][end]; // is already memorized

        if((s[start] == '(' || s[start] == '*') 
           && (s[end] == ')'|| s[end] == '*') 
           && isValid(s, start + 1, end - 1))
            return f[start][end] = 1;

        for(int i = start; i < end; i++){
            if(isValid(s, start, i) && isValid(s, i + 1, end)) 
                return f[start][end] = 1;
        }

        return f[start][end] = 0;
    }

};

Code: Ordered DP with memoization Time: O(n^3) Space: O(n^2), Bottom Up

class Solution {
public:
    bool checkValidString(const string& s) {
        int l = s.length();
        if (l == 0) return true;
        vector<vector<int>> dp(l, vector<int>(l, 0));
        for (int i = 0; i < l; ++i)
            if (s[i] == '*') dp[i][i] = 1;
        for (int len = 2; len <= l; ++len)
            for (int i = 0; i <= l - len; ++i) {
                int j = i + len - 1;
                // (...), *...), (...*, *...*
                if ((s[i] == '(' || s[i] == '*')
                  &&(s[j] == ')' || s[j] == '*'))
                    if (len == 2 || dp[i + 1][j - 1]) {
                        dp[i][j] = 1;
                        continue;                    
                    }

                for (int k = i; k < j; ++k)
                    if (dp[i][k] && dp[k + 1][j]) {
                        dp[i][j] = 1;
                        break;
                    }
            }
        return dp[0][l - 1];
    }
};

Code Counting Time: O(n), Space: O(1)

class Solution {
public:
    bool checkValidString(string s) {
        int max_open_left = 0, min_open_left = 0;
        for(char c: s){
            if(c == '(') min_open_left++; else min_open_left--;
            if(c != ')') max_open_left++; else max_open_left--;
            if(max_open_left < 0) return false;
            min_open_left = max(0, min_open_left); // we cannot use previous "*" to fullfill later '(": reset the min_open_left
        }

        return min_open_left == 0;
    }
};

class Solution {
public:
    bool checkValidString(string s) {
        int max_open_left = 0, min_open_left = 0;
        for(char c: s){
            if(c == '(') min_open_left++; else if(min_open_left > 0) min_open_left--;
            if(c != ')') max_open_left++; 
            else if (max_open_left == 0) return false; 
            else max_open_left--;
        }

        return min_open_left == 0;
    }
};

Python

class Solution(object):
    def checkValidString(self, s):
        """
        :type s: str
        :rtype: bool
        """
        max_open, min_open = 0, 0

        for c in s:
            # if c == '(': min_open += 1 
            # else: min_open -=1
            min_open = min_open + 1 if c == '(' else min_open - 1
            max_open = max_open + 1 if c != ')' else max_open - 1

            if max_open < 0: return False
            min_open = max(0, min_open)

        return min_open == 0

Special Thanks to Huahua's blog