来源Leetcode第44题通配符匹配
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*‘ 的通配符匹配。
- ‘?’ 可以匹配任何单个字符。
‘*‘ 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。说明:
s 可能为空，且只包含从 a-z 的小写字母。
- p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
示例 2:
输入:
s = “aa”
p = “*“
输出: true
解释: ‘*‘ 可以匹配任意字符串。
和之前那题正则表达式匹配略有不同。
代码同第10题：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
class Solution {
//Method one
//采用数组memo标记i j位置的匹配情况
Boolean[][] memo;
public boolean isMatch(String s, String p) {
memo = new Boolean[s.length() + 1][p.length() + 1];
return isMatch(s.toCharArray(), 0, p.toCharArray(), 0);
}
//两个参数分别为匹配串和模式串
//i j 分别对应两个字符串起始位置
private boolean isMatch(char[] ss, int i, char[] ps, int j) {
//这一句重点，如果memo备忘录有值说明这里已经匹配过了
if(memo[i][j] != null) return memo[i][j];
boolean result = false;
//如果已经到了模式串尾，需检查匹配串
if(j == ps.length) {
result = (i == ss.length);
} else {
//第一次匹配的情况
boolean firstMatch = i != ss.length && (ss[i] == ps[j] || ps[j] == '?');
//如果模式串开头为'*‘
//意味着可以跳过当前匹配串的字符或者跳过当前模式串中的字符
if(ps[j] == '*') {
result = (i != ss.length && isMatch(ss, i + 1, ps, j)) || isMatch(ss, i, ps, j + 1);
} else {
//不为'*'
//则要检查初次是否匹配以及剩下的是否匹配
result = firstMatch && isMatch(ss, i + 1, ps, j + 1);
}
}
//写入结果到memo备忘录里
memo[i][j] = result;
return result;
}
//Method Two
public boolean isMatch(String text, String pattern) {
// 多一维的空间，因为求 dp[len - 1][j] 的时候需要知道 dp[len][j] 的情况，
// 多一维的话，就可以把 对 dp[len - 1][j] 也写进循环了
boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
// dp[len][len] 代表两个空串是否匹配了，"" 和 "" ，当然是 true 了。
dp[text.length()][pattern.length()] = true;
// 从 len 开始减少
for (int i = text.length(); i >= 0; i--) {
for (int j = pattern.length(); j >= 0; j--) {
// dp[text.length()][pattern.length()] 已经进行了初始化
if (i == text.length() && j == pattern.length())
continue;
//相比之前增加了判断是否等于 *
boolean first_match = (i < text.length() && j < pattern.length() && (pattern.charAt(j) == text.charAt(i) || pattern.charAt(j) == '?' || pattern.charAt(j) == '*'));
if (j < pattern.length() && pattern.charAt(j) == '*') {
//将 * 跳过 和将字符匹配一个并且 pattern 不变两种情况
dp[i][j] = dp[i][j + 1] || first_match && dp[i + 1][j];
} else {
dp[i][j] = first_match && dp[i + 1][j + 1];
}
}
}
return dp[0][0];
}
//Method Three
boolean isMatch(String str, String pattern) {
int s = 0, p = 0, match = 0, starIdx = -1;
//遍历整个字符串
while (s < str.length()){
// 一对一匹配，两指针同时后移。
if (p < pattern.length() && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){
s++;
p++;
}
// 碰到 *，假设它匹配空串，并且用 startIdx 记录 * 的位置，记录当前字符串的位置，p 后移
else if (p < pattern.length() && pattern.charAt(p) == '*'){
starIdx = p;
match = s;
p++;
}
// 当前字符不匹配，并且也没有 *，回退
// p 回到 * 的下一个位置
// match 更新到下一个位置
// s 回到更新后的 match
// 这步代表用 * 匹配了一个字符
else if (starIdx != -1){
p = starIdx + 1;
match++;
s = match;
}
//字符不匹配，也没有 *，返回 false
else return false;
}
//将末尾多余的 * 直接匹配空串 例如 text = ab, pattern = a*******
while (p < pattern.length() && pattern.charAt(p) == '*')
p++;
return p == pattern.length();
}
}