通配符匹配
用$dp[i][j]$表示字符串s的前i个字符和模式p的前j个字符的匹配情况，一共有三种情况。
- $p[j]$是小写字母
$$
dp[i][j] = dp[i-1][j-1] \wedge (s[i]==p[j])
$$
- $p[j]$是$’?’$
$$
dp[i][j] = dp[i-1][j-1]
$$
- $p[j]$是$’*’$，那么有两种情况，第一种是模式p使用星号，第二种是模式p不使用星号。
$$
dp[i][j] = dp[i-1][j] \vee dp[i][j-1]
$$
还有需要讨论边界情况，即$i=0$和$j=0$的情况：
- $dp[0][0]=true$
- $dp[0][j]=dp[0][j-1] \wedge (p[j]==’*’)$
- $dp[i][0]=false$
1 | class Solution { |
2 | public boolean isMatch(String s, String p) { |
3 | int sLen = s.length(); |
4 | int pLen = p.length(); |
5 | boolean[][] dp = new boolean[sLen+1][pLen+1]; |
6 | dp[0][0] = true; |
7 | for(int i=1; i<=pLen; i++){ |
8 | dp[0][i] = dp[0][i-1] && (p.charAt(i-1)=='*'); |
9 | } |
10 | for(int i=1; i<=sLen; i++){ |
11 | for(int j=1; j<=pLen; j++){ |
12 | if(p.charAt(j-1)>='a' && p.charAt(j-1)<='z'){ |
13 | dp[i][j] = dp[i-1][j-1] && (s.charAt(i-1)==p.charAt(j-1)); |
14 | }else if(p.charAt(j-1) == '?'){ |
15 | dp[i][j] = dp[i-1][j-1]; |
16 | }else{ |
17 | dp[i][j] = dp[i-1][j] || dp[i][j-1]; |
18 | } |
19 | } |
20 | } |
21 | return dp[sLen][pLen]; |
22 | } |
23 | } |
复杂度分析：
- 时间复杂度：$O(mn)$，m是字符串s的长度，n是模式p的长度。
- 空间复杂度：$O(mn)$。