题目
方法一-动态规划
思路：
假设主串 s s s 长度为 n n n，模式串 p p p 长度为 m m m，考虑模式串 p p p 的最后一个字符：
- p p p 的最后一个字符是 a-z 的小写字母，则看该字符是否能和主串中最后一个字符匹配，也就是看 s [ n − 1 ] s[n-1] s[n−1] 和 p [ m − 1 ] p[m-1] p[m−1] 是否相等，相等的话就继续往前看 s 0... n − 2 s_{0...n-2} s0...n−2 和 p 0... m − 2 p_{0...m-2} p0...m−2 ，不等的话直接返回 f a l s e false false
- p p p 的最后一个字符是"."，能与任意字符匹配，所以继续往前看 s 0... n − 2 s_{0...n-2} s0...n−2 和 p 0... m − 2 p_{0...m-2} p0...m−2
-
p
p
p 的最后一个字符是"*"，表示
p
[
m
−
2
]
=
c
p[m-2]=c
p[m−2]=c 可以重复 0 次或多次，这时可以将
p
[
m
−
2
]
p[m-2]
p[m−2] 和
p
[
m
−
1
]
p[m-1]
p[m−1] 看作一个整体
c
∗
c*
c∗：
若 s [ n − 1 ] s[n-1] s[n−1] 不是 c，则看 s 0... n − 1 s_{0...n-1} s0...n−1 和 p 0... m − 3 p_{0...m-3} p0...m−3是否匹配；
若 s [ n − 1 ] s[n-1] s[n−1] 是 c 或者 c = ′ . ′ c=' .' c=′.′，则主串继续向前看，考虑 s 0... n − 2 s_{0...n-2} s0...n−2 和 p 0... m − 1 p_{0...m-1} p0...m−1是否匹配
转移方程：
用 f [ i ] [ j ] f[i][j] f[i][j] 表示 s s s 的前 i 个字符与 p p p 的前 j 个字符能否匹配。
- 前两种情况可以合并为： f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] f[i][j]=f[i-1][j-1] f[i][j]=f[i−1][j−1]
- 第三种情况可以分成看
c
∗
c*
c∗ 和不看
c
∗
c*
c∗ 两种情况：
不看 c ∗ c* c∗ （即 s [ n − 1 ] s[n-1] s[n−1] 不是 c）： f [ i ] [ j ] = f [ i ] [ j − 2 ] f[i][j]=f[i][j-2] f[i][j]=f[i][j−2]
看 c ∗ c* c∗（即 s [ n − 1 ] s[n-1] s[n−1] 是 c 或者 c = ′ . ′ c=' .' c=′.′） ： f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i][j]=f[i-1][j] f[i][j]=f[i−1][j]
初始条件：
- 主串和模式串均为空串：直接返回 t r u e true true
- 模式串为空，主串非空：直接返回 f a l s e false false
- 其他情况需要计算
代码：
class Solution {
public boolean isMatch(String s, String p) {
int n = s.length();
int m = p.length();
boolean[][] f = new boolean[n + 1][m + 1];
for(int i = 0; i <= n; i++){
for(int j = 0; j <= m; j++){
//若模式串为空，主串也为空匹配成功，主串非空匹配失败
if(j == 0){
f[i][j] = (i == 0) ? true : false;
}else{//模式串非空，分别考虑*和非*两种情况下的转移
if(p.charAt(j - 1) != '*'){
if(i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')){
f[i][j] = f[i - 1][j - 1];
}
}else{//*情况下，分别考虑看c*和不看c*两种情况
//不看c*
if(j >= 2){
f[i][j] = f[i][j - 2];
}
//看c*
if(i >= 1 && j >= 2 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')){
f[i][j] |= f[i - 1][j];
}
}
}
}
}
return f[n][m];
}
}
notes：先算的是不看星号的情况，再算看星号的情况，即，对于 f [ i ] [ j ] f[i][j] f[i][j] 我们计算了两次，如果在不看星号时已经得到了 t r u e true true 的结果，那么无论在看星号时得到的结果是什么， f [ i ] [ j ] f[i][j] f[i][j] 都应该保持 t r u e true true 不变。也就是说，只要两次计算中有一种情况能匹配，结果就是 t r u e true true ，所以用的是 ∣ = |= ∣= 而非 = = =
复杂度：
- 时间复杂度： O ( m n ) O(mn) O(mn)，需要计算出所有 f [ i ] [ j ] f[i][j] f[i][j] 的值，每个状态在进行转移时时间开销为 O ( 1 ) O(1) O(1)
- 空间复杂度： O ( m n ) O(mn) O(mn)，即存储所有 f [ i ] [ j ] f[i][j] f[i][j] 所占用的空间