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 ')'.
public boolean checkValidString(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
for (int i = 0;
i < n;
i++) {
if (s.charAt(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.charAt(i) == '(' && s.charAt(j) == ')') {
dp[i][j] = dp[i + 1][j - 1];
}
else if (s.charAt(i) == '*' && (s.charAt(j) == ')' || s.charAt(j) == '*')) {
dp[i][j] = dp[i + 1][j] || (j > i && dp[i][j - 1]);
}
else if (s.charAt(j) == '*' && (s.charAt(i) == '(' || s.charAt(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?
