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 ')'.
def checkValidString(s):
n = len(s)
dp = [[False] * n for _ in range(n)]
for i in range(n):
if s[i] == '*':
dp[i][i] = True
for length in range(1, n):
for i in range(n - length):
j = i + length
if s[i] == '(' and s[j] == ')':
dp[i][j] = dp[i + 1][j - 1]
elif s[i] == '*' and (s[j] == ')' or s[j] == '*'):
dp[i][j] = dp[i + 1][j] or (j > i and dp[i][j - 1])
elif s[j] == '*' and (s[i] == '(' or s[i] == '*'):
dp[i][j] = dp[i][j - 1] or (j > i and dp[i + 1][j])
return dp[0][n - 1]Follow-up:
Can you solve this problem using a stack?
