Valid Parenthesis String
Given a string containing just the characters '(', ')', and '*', return true if the string is valid. The string is valid if it can be interpreted as a sequence of valid parentheses pairs. '*' can be treated as either '(' or ')'.
Constraints:
- 1 <= s.length <= 100
- s[i] is '(', ')' or '*'.
Examples:
Input: "(*)"
Output: true
Explanation: The string can be interpreted as "( )".
Input: "(*)()"
Output: true
Explanation: The string can be interpreted as "( )( )".
Input: "*)"
Output: false
Explanation: There is no way to interpret the string as a sequence of valid parentheses pairs.
Solutions
Dynamic Programming
The solution uses dynamic programming to build up a table of valid strings. It starts by initializing the diagonal of the table to true for '*' characters. Then it fills in the rest of the table by checking if the current string can be made valid by matching '(' and ')' characters or by using '*' characters as either '(' or ')'.
class Solution {
public:
bool checkValidString(string s) {
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n, false));
for (int i = 0;
i < n;
i++) {
if (s[i] == '*') {
dp[i][i] = true;
}
}
for (int len = 1;
len < n;
len++) {
for (int i = 0;
i < n - len;
i++) {
int j = i + len;
if (s[i] == '(' && s[j] == ')') {
dp[i][j] = dp[i + 1][j - 1];
}
else if (s[i] == '*' && (s[j] == ')' || s[j] == '*')) {
dp[i][j] = dp[i + 1][j] || (j > i && dp[i][j - 1]);
}
else if (s[j] == '*' && (s[i] == '(' || s[i] == '*')) {
dp[i][j] = dp[i][j - 1] || (j > i && dp[i + 1][j]);
}
}
}
return dp[0][n - 1];
}
}
;Follow-up:
Can you solve this problem using a stack?
