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”, “c*a*b”) → false
题目理解：
经典的字符串匹配问题。
首先想到的方法，顺着走，但是第一次写得非常复杂，这里忽略不计（但是速度还可以）。
今天所想的方法，动态规划，自顶向下，或者自底向上。
看了别人的顺着走的算法，原来思路也是很简单的。
所以不是看到这种问题就想着动态规划，也许顺着想就能简单解决。
另外，这道题的java运行时间十分不稳定，重复提交可以差30ms。
代码一：
自顶向下。
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
| public class Solution {
public boolean isMatch(String s, String p) {
char[] ss = s.toCharArray(), pp = p.toCharArray();
char[] ppp = new char[pp.length];
int ppp_idx = 0;
boolean last_not_star = true;
for ( int i = 0; i < pp.length; i++ ) {
if ( pp[i] == '*' ) {
if ( last_not_star )
ppp[ppp_idx++] = pp[i];
last_not_star = false;
} else {
last_not_star = true;
ppp[ppp_idx++] = pp[i];
}
}
char[] pppp = new char[ppp_idx];
for ( int i = 0; i < ppp_idx; i++ )
pppp[i] = ppp[i];
pp = pppp;
char[][] matchs = new char[ss.length + 1][pp.length + 1];
for ( int i = 0; i < ss.length; i++ )
matchs[i][pp.length] = '0';
matchs[ss.length][pp.length] = '1';
return myMatch( ss, pp, 0, 0, matchs) == '1';
}
private char myMatch(char[] a, char[] b, int ai, int bi, char[][] matchs) {
if ( matchs[ai][bi] != '\0' )
return matchs[ai][bi];
if ( ai == a.length ) {
if ( b[bi] == '*' )
matchs[ai][bi] = myMatch(a, b, ai, bi + 1, matchs);
else
matchs[ai][bi] = '0';
return matchs[ai][bi];
}
if ( b[bi] == '?' ) {
matchs[ai][bi] = myMatch(a, b, ai + 1, bi + 1, matchs);
} else if ( b[bi] == '*' ) {
matchs[ai][bi] = myMatch(a, b, ai, bi + 1, matchs);
if ( matchs[ai][bi] != '1' )
matchs[ai][bi] = myMatch(a, b, ai + 1, bi, matchs);
} else {
if ( a[ai] == b[bi] )
matchs[ai][bi] = myMatch(a, b, ai + 1, bi + 1, matchs);
else
matchs[ai][bi] = '0';
}
return matchs[ai][bi];
}
}
|
复杂度：O(mn)？？？
运行时间：大约100ms。
击败：大约16.73%
代码二：
自底向上。
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 class Solution {
public boolean isMatch(String s, String p) {
char[] ss = s.toCharArray(), pp = p.toCharArray();
int m = ss.length, n = pp.length;
boolean[][] matchs = new boolean[m + 1][n + 1];
for ( int i = 0; i <= m; i++ )
matchs[i][0] = false;
for ( int i = 0; i < n && pp[i] == '*'; i++ )
matchs[0][i+1] = true;
matchs[0][0] = true;
for ( int i = 1; i <= m; i++ ) {
for ( int j = 1; j <= n; j++ ) {
int ii = i - 1, jj = j - 1;
if ( pp[jj] == '?' )
matchs[i][j] = matchs[ii][jj];
else if ( pp[jj] == '*' )
matchs[i][j] = matchs[ii][j] || matchs[i][jj];
else {
if ( matchs[ii][jj] )
matchs[i][j] = (ss[ii] == pp[jj]);
}
}
}
return matchs[m][n];
}
}
|
复杂度：O(mn)。
运行时间：大约75ms。
击败：大约50%
代码三：
顺序扫描。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public class Solution {
public boolean isMatch(String s, String p) {
char[] ss = s.toCharArray(), pp = p.toCharArray();
int m = ss.length, n = pp.length, i = 0, j = 0, star_idx = -1, match = -1;
while ( i < m ) {
if ( j < n && pp[j] == '*' ) {
match = i;
star_idx = j;
j++;
} else if ( j < n && ( pp[j] == '?' || pp[j] == ss[i] ) ) {
i++;
j++;
} else if ( star_idx != -1 ) {
i = match++;
j = star_idx + 1;
} else return false;
}
while ( j < n && pp[j] == '*' )
j++;
return j == n;
}
}
|
复杂度：应该介于O(mn)到O(m + n)之间。
运行时间： 大约60ms。
击败：大约80%
