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 ')'.
function checkValidString(s) {
const n = s.length;
const dp = Array(n)
.fill(0)
.map(() => Array(n).fill(false));
for (let i = 0; i < n; i++) {
if (s[i] === '*') {
dp[i][i] = true;
}
}
for (let len = 1; len < n; len++) {
for (let i = 0; i < n - len; i++) {
const 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?
