slt
Solutuion 1 递归
注意*
一定是match preceding char,*
不会出现在第一个位置
Solutuion 2 DP
dp[i][j]: if s[0..i-1] matches p[0..j-1]
if p[j-1] != '*':
dp[i][j] = dp[i-1][j-1] && s[i-1] == p[j-1]
if p[j-1] == '*': (denote p[j-2] with x)
dp[i][j] is true iff any of the following is true
1) "x*" repeats 0 time and matches empty: dp[i][j-2]
2) "x*" repeats >= 1 times and matches "x*x": s[i-1] == x && dp[i-1][j]
Last updated
Was this helpful?