Leetcode
Dynamic Programming
44 Wildcard Matching

1. Question

Implement wildcard pattern matching with support for'?'and'*'.
1
'?' Matches any single character.
2
'*' Matches any sequence of characters (including the empty sequence).
3
4
The matching should cover the
5
entire
6
input string (not partial).
7
8
The function prototype should be:
9
bool isMatch(const char *s, const char *p)
10
11
Some examples:
12
isMatch("aa","a") → false
13
isMatch("aa","aa") → true
14
isMatch("aaa","aa") → false
15
isMatch("aa", "*") → true
16
isMatch("aa", "a*") → true
17
isMatch("ab", "?*") → true
18
isMatch("aab", "c*a*b") → false
Copied!

2. Implementation

(1) Two Pointers
1
class Solution {
2
public boolean isMatch(String s, String p) {
3
int sIndex = 0, pIndex = 0;
4
int matchIndex = -1, starIndex = -1;
5
6
while (sIndex < s.length()) {
7
// case 1: p.charAt(pIndex) == s.charAt(sIndex) 或者 p.charAt(pIndex) == ?时, pIndex所在的位置匹配sIndex的字符
8
// 同时移动pIndex和sIndex
9
if (pIndex < p.length() && (p.charAt(pIndex) == s.charAt(sIndex) || p.charAt(pIndex) == '?')) {
10
++pIndex;
11
++sIndex;
12
}
13
// case 2: 如果p.charAt(pIndex)为*, 此时的*可能不匹配任何s的子串,所以保留starIndex,之后可能会用到,并且我们先不移动sIndex
14
// (因为*可能不匹配任何s的子串), 并
15
else if (pIndex < p.length() && p.charAt(pIndex) == '*') {
16
starIndex = pIndex;
17
++pIndex;
18
// 此时的 sIndex 还不确定是否要被 * 表示,需要继续从sIndex开始遍历,如果后面某个位置发生匹配错误,
19
// 则表示sIndex应该被*表示,重新回复从 sIndex+1 开始重新匹配
20
matchIndex = sIndex;
21
}
22
// case 3: 匹配失败,说明matchIndex指向的字符应该被*表示,回溯到matchIndex+1,重新开始进行 starIndex+1和matchIndex+1匹配
23
else if (starIndex > -1) {
24
pIndex = starIndex + 1;
25
sIndex = matchIndex + 1;
26
++matchIndex;
27
}
28
else {
29
return false;
30
}
31
}
32
33
//s已经遍历完,p按理最多只剩下*,如果还存在非*字母,则匹配失败
34
while (pIndex < p.length() && p.charAt(pIndex) == '*') {
35
++pIndex;
36
}
37
return pIndex == p.length();
38
}
39
}
Copied!
(2) DP
解析
1
class Solution {
2
public boolean isMatch(String s, String p) {
3
int m = s.length(), n = p.length();
4
boolean[][] dp = new boolean[m + 1][n + 1];
5
6
dp[0][0] = true;
7
8
for (int j = 1; j <= n; j++) {
9
if (p.charAt(j - 1) == '*') {
10
dp[0][j] = dp[0][j - 1];
11
}
12
}
13
14
for (int i = 1; i <= m; i++) {
15
for (int j = 1; j <= n; j++) {
16
if (p.charAt(j - 1) == '*') {
17
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
18
}
19
else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
20
dp[i][j] = dp[i - 1][j - 1];
21
}
22
else {
23
dp[i][j] = false;
24
}
25
}
26
}
27
return dp[m][n];
28
}
29
}
Copied!

3. Time & Space Complexity

Two Pointers: 时间复杂度O(mn), 空间复杂度O(1)
DP: 时间复杂度O(mn), 空间复杂度O(mn)