题目
- 题目来源: 10. 正则表达式匹配
- 题目描述
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符'*' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
- 示例1：
输入： s = "aa" p = "a"
输出： false
解释： "a" 无法匹配 "aa" 整个字符串
- 示例2:
输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
- 示例3
输入： s = "ab" p = "."
输出： true
解释：".*"表示可匹配零个或多个（''）任意字符（'.'）。
解析
首先读完题目，可以发现这是一道比较明显的动态规划题目，但本题目的状态转移方程的确有几分难想，接下来咱们来一起捋一下
明确 dp[i][j] 代表什么
dp[i][j]: 表示字符串s的前 i 个字符和字符串 p 的前 j 个字符是否匹配，结果为 布尔类型
分析状态转移
对于字符串 p ，有三种可能:
- 小写字母: 由于是小写字母，因此只需判断 s[i] 与 p[j] 是否相等即可
- 若 s[i] == p[j] ，dp[i][j] = dp[i - 1][j - 1]
- 若 s[i] != p[j] ，dp[i][j] = false
- 点号
.：可以匹配任一字符，dp[i][j] = dp[i - 1][j - 1]; - 星号
*
星号比较难处理，咱们单独拉出来
- 分析星号情况
星号的意思是可以匹配0次或者多次
- s[i]与p[j-1]不匹配: 对于不匹配来说，应当满足下面条件，s[i] != p[j-1] 和 p[j-1] != '.'， 此时 dp[i][j] = dp[i][j - 2]
- s[i]与p[j-1]匹配: 有两种情况，可以是匹配多次(dp[i][j] = dp[i-1][j])，也可能是匹配一次(dp[i][j] = dp[i][j-1])，但是匹配多次情况是包括匹配一次的。
下面举个栗子来深入说明一下这点:
s = “afs”，p = "afs*"
匹配多次：dp[3][4] = dp[2][4]
匹配一次：dp[3][4] = dp[3][3]
其实结果上是一样的，都是true，只不过这里dp[2][4]表示不使用"s*"时，s与p匹配，而dp[3][3]是直接匹配。
所以由上我们得到此种情况下的结论：dp[i][j] = dp[i-1][j]？
和不匹配时相同，上面这样分析，我们又漏掉了 p[j-1] = '.' 的情况，下面再举个例子
- s = "ab"，p = "ab.*"，
dp[2][4]应该是true，但是按照上面的写法的话dp[2][4] = dp[1][4]就是false，这里应该匹配零次".*"，即：dp[2][4] = dp[2][2]。
因此，正确的结论是：dp[i][j] = dp[i-1][j] || dp[i][j - 2];
边界情况
- dp[0][0] = true;
- dp[i][0] = false; (i > 0)
- dp[0][j](j > 0)可能为true
总结
分析完上面部分，其实整个题目的脉络就很清晰了，只需要将上面的分析过程翻译成代码。
