#Problem

#⭐️⭐️⭐️⭐️⭐️

Wildcard Matching

#Solution

Dynamic Programming

dp[i][j]表示s中前i个字符串和p中前j个字符串是否匹配.

if p[j - 1] != ‘*’:
dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == ‘?’)

else:
dp[k..i][j] = true, if dp[k][j - 1] = true

#Initialization:

dp[0][j] = dp[0][j - 1] && p[j - 1] == ‘*’

只有当[0..j]都是*的情况下dp[0][j]才可能是true.

#Code

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
class Solution {
public boolean isMatch(String s, String p) {
if (s.isEmpty() && p.isEmpty()) return true;
if (p.isEmpty()) return false;
int m = s.length();
int n = p.length();
char[] charS = s.toCharArray();
char[] charP = p.toCharArray();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int j = 1; j <= n; j++) {
dp[0][j] = dp[0][j - 1] && charP[j - 1] == '*';
}
for (int j = 1; j <= n; j++) {
if (charP[j - 1] == '*') {
int i = 0;
while (i <= m && !dp[i][j - 1]) {
i++;
}
while (i <= m) {
dp[i][j] = true;
i++;
}
} else {
for (int i = 1; i <= m; i++) {
dp[i][j] = dp[i - 1][j - 1] && (charS[i - 1] == charP[j - 1] || charP[j - 1] == '?');
}
}
}
return dp[m][n];
}
}

Comments