给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。
星号 * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
一个空字符串也被视为有效字符串。
示例 1:

输入: “()”
输出: True
示例 2:

输入: “(*)”
输出: True
示例 3:

输入: “(*))”
输出: True

dp[i][j] 表示字符串 s 从下标 i 到 j 的子串是否为有效的括号字符串, 0≤i≤j

动态规划的边界情况是子串的长度为 1或2的情况:
当子串的长度为 1 时，只有当该字符是 ‘*’ 时，才是有效的括号字符串，此时子串可以看成空字符串；
当子串的长度为 2时，只有当第一个字符是 "(或 * “且第二个字符是 " * 或)” 时，才是有效的括号字符串

当子串的长度大于 2 时，需要根据子串的首尾字符以及中间的字符判断子串是否为有效的括号字符串。只要满足以下一个条件就有可以：
1 如果当s[i] 是 “(或 * “且 s[j]是” * 或)” 时
dp[i+1][j−1]=true 时 dp[i][j]=true，dp[i+1][j−1]=False 时 dp[i][j]=False

2 如果存在 i≤k

时间复杂度：O(n3), 有O(n2)个状态，每个状态的计算时间最多为O(n)。
空间复杂度：O(n2)

class Solution:def checkValidString(self, s: str) -> bool:n = len(s)dp = [[False]*n for _ in range(n)]for i in range(n):if s[i] == '*':dp[i][i] = Truefor i in range(n-1):if (s[i] in ['(', '*']) and (s[i+1] in [')', '*']):dp[i][i+1] = Truefor i in range(n-3, -1, -1):for j in range(i+2, n):if (s[i] in ['(', '*']) and (s[j] in [')', '*']):dp[i][j] = dp[i+1][j-1]for k in range(i, j):if dp[i][k] and dp[k+1][j]:dp[i][j] = True break  return dp[0][n-1]

可以看到时间复杂度比较高，用栈的话能降低。一般遇到括号匹配问题就可以想到栈。
在有星号的情况下，需要两个栈分别存储左括号和星号。从左到右遍历字符串，进行如下操作。
1 如果遇到左括号，则将当前下标存入左括号栈。
2 如果遇到星号，则将当前下标存入星号栈。
3 如果遇到右括号，则需要有一个左括号或星号和右括号匹配，由于星号也可以看成右括号或者空字符串，因此当前的右括号应优先和左括号匹配，没有左括号时和星号匹配：
3.1 如果左括号栈不为空，则从左括号栈弹出栈顶元素；
3.2 如果左括号栈为空且星号栈不为空，则从星号栈弹出栈顶元素；
3.3 如果左括号栈和星号栈都为空，则没有字符可以和当前的右括号匹配，返回 false

遍历结束之后，左括号栈和星号栈可能还有元素。为了将每个左括号匹配，需要将星号看成右括号，且每个左括号必须出现在其匹配的星号之前。当两个栈都不为空时，每次从左括号栈和星号栈分别弹出栈顶元素，对应左括号下标和星号下标，判断左括号下标小于星号下标，如果左括号下标大于星号下标则返回 false。最终判断左括号栈是否为空。如果左括号栈为空，则左括号全部匹配完毕，剩下的星号都可以看成空字符串，此时返回 true。如果左括号栈不为空，则还有左括号无法匹配，此时返回 false。

时间复杂度O(n), 空间复杂度O(n)

class Solution:def checkValidString(self, s: str) -> bool:n = len(s)left_stack, star_stack = [], []for i in range(n):if s[i] == '(':left_stack.append(i)elif s[i] == '*':star_stack.append(i)elif s[i] == ')':if left_stack:left_stack.pop()elif star_stack:star_stack.pop()else:return False i, j = len(left_stack)-1, len(star_stack) - 1while (i >= 0) and (j >= 0):left_index = left_stack.pop()right_index = star_stack.pop()if left_index >= right_index:return Falsei -= 1j -= 1if i < 0:return Trueelse:return False