Wildcard Matching
Implement wildcard pattern matching with support for ‘?’ and ‘*’.
‘?’ Matches any single character.
‘*’ Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “*”) → true
isMatch(“aa”, “a*”) → true
isMatch(“ab”, “?*”) → true
isMatch(“aab”, “cab”) → false
https://leetcode.com/problems/wildcard-matching/
基于DP的解法一（二维数组）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public boolean isMatch(String s, String p) {
if(s == null || p == null) return false;
if (p.replace("*", "").length() > s.length())
return false;
if(s.length() == 0) return true;
boolean[][] dp = new boolean[p.length() + 1][s.length() + 1];
dp[0][0] = true;
for(int i = 0; i < p.length(); ++i) {
if(p.charAt(i) == '*') dp[i + 1][0] = dp[i][0];
for(int j = 0; j < s.length(); ++j) {
if(p.charAt(i) == '*')
dp[i + 1][j + 1] = dp[i][j + 1] || dp[i + 1][j] ;
else
dp[i + 1][j + 1] = dp[i][j] && (p.charAt(i) == '?' || s.charAt(j) == p.charAt(i));
}
}
return dp[p.length()][s.length()];
}
|
基于DP的解法二（一维数组）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public boolean isMatch(String s, String p) {
if(s == null || p == null) return false;
if (p.replace("*", "").length() > s.length())
return false;
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for(int i = 0; i < p.length(); ++i) {
if(p.charAt(i) == '*') {
for(int j = 0; j < s.length(); ++j)
dp[j + 1] = dp[j] || dp[j + 1];
} else {
for(int j = s.length() - 1; j >= 0; --j)
dp[j + 1] = (s.charAt(j) == p.charAt(i) || p.charAt(i) == '?') && dp[j];
dp[0] = dp[0] && p.charAt(i) == '*';
}
}
return dp[s.length()];
}
|
基于回溯的解法
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
| public boolean isMatch(String s, String p) {
if(s == null || p == null) return false;
int i = 0, j = 0;
int tj = -1, ti = -1;
while(i < s.length()) {
if(j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
++i;
++j;
}else if(j < p.length() && p.charAt(j) == '*') {
while(j < p.length() && p.charAt(j) == '*') ++j;
ti = i;
tj = j;
if(tj == p.length()) return true;
}else if(tj != -1 && (j == p.length() || s.charAt(i) != p.charAt(j))) {
i = ++ti;
j = tj;
} else
return false;
}
while(j < p.length())
if(p.charAt(j) != '*')
return false;
else
++j;
return true;
}
|