## 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