困难 警告!
想都不要想,直接看答案
本文答案参考自leetcode官方
【方法一】动态规划(DP)
动态规划的一般解法:
- 创建二维数组存放某些东西
- 确定状态转移方程
- 确定边界条件
- 开始
对这道题,这个二维数组 f[i][j] 表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配
- 如果 s 的第 i 个字符与 p 的第 j 个字符相同,则 f[i][j] = f[i - 1][j - 1] ,因为你后面匹配了那前面也肯定匹配
- 如果 s 的第 i 个字符与 p 的第 j 个字符不相同,则 f[i][j] = false
- 如果 p 的第 j 个字符是 *,在匹配不到(0次)的情况下, f[i][j] = f[i][j - 2],即星号和前面的字符相当于不存在(不影响结果)
- 如果 p 的第 j 个字符是 *,在匹配到 1次 的情况下 ,f[i][j] = f[i][j - 2]
- 如果 p 的第 j 个字符是 *,在匹配到(多于1次,设为n)的情况下 f[i][j] = f[i - n][j - 2],同样是因为后面匹配了那前面也肯定匹配,这里具体操作是循环执行 f[i][j] = f[i - 1][j] n - 1次,然后执行 f[i][j] = f[i][j - 2],官方给出了精巧的状态转移方程:(我难以表达出其精巧之处,反正就是精巧)
- 如果 p 的第 j 个字符是 . ,则必定匹配
最终状态转移方程为:
这里最好结合画图来理解(但是我懒~)
边界条件为:f[0][0] = true
答案为 f[m][n] ,其中 m 和 n 分别是字符串 s 和 p 的长度
因为本人水平有限,如果以上内容有误,不用走程序,直接骂吧~[捂脸]