[Hot100]10.正则表达式匹配

10. 正则表达式匹配
困难题
动态规划：
dp[i][j] 表示 s 的前 i 个是否能被 p 的前 j 个匹配

● 转移方程： 需要注意，由于 dp[0][0] 代表的是空字符的状态， 因此 dp[i][j] 对应的添加字符是 s[i - 1] 和 p[j - 1] 。
○ 当 p[j - 1] = ‘*’ 时， dp[i][j] 在当以下任一情况为 true时等于true ：
■ dp[i][j-2]
● 将字符组合 p[j - 2] * 看作出现 0 次时，能否匹配；
■ dp[i-1][j]
● 且 p[j - 2] = s[i - 1]： 即让字符 p[j - 2]多出现 1 次时，能否匹配；
● 且 p[j - 2] = ‘.’：即让字符 ‘.’ 多出现 1 次时，能否匹配；

○ 当 p[j - 1] != ‘*’ 时， dp[i][j] 在当以下任一情况为true 时等于 true ：
■ dp[i - 1][j - 1]
● 且 s[i - 1] = p[j - 1]： 即让字符 p[j - 1] 多出现一次时，能否匹配；
● 且 p[j - 1] = ‘.’： 即将字符 . 看作字符 s[i - 1] 时，能否匹配；

class