首页 > 代码库 > LeetCode: Wildcard Matching 解题报告
LeetCode: Wildcard Matching 解题报告
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", "c*a*b") → false
SOLUTION 1:
DP.
动态规划：输入两个字符串s,p(p包含通配符，用p去匹配s),用flag[i][j]表示字符串p从0到i的的子字符串能否匹配s从0到j的子字符串，我们可以得到如下递推公式：
如果p.charAt(i)==s.charAt(j)或则p.charAt(i)==‘?‘,相当于将最后一个字符匹配掉，所以
flag[i][j]=flag[i-1][j-1];
如果p.charAt(i)==‘*‘，‘*‘可以选择匹配0个字符，此时flag[i][j]=flag[i-1][j];可以选择匹配1个字符，此时flag[i][j]=flag[i-1][j-1];……所以，
flag[i][j]=flag[i-1][j]||flag[i-1][j-1]||……||flag[i-1][0]。
但是上面的公式可以化简，当p.charAt(i)==‘*‘时,有
flag[i][j-1]=flag[i-1][j-1]||flag[i-1][j-2]||……||flag[i-1][0]
所以
flag[i][j]==flag[i-1][j]||flag[i][j-1],所以综合递推公式如下：
空间复杂度？
由上面的公式可以看出，flag[i][j]只与第i行和第i-1行相关，所以只需要开辟两个一维数组即可。空间复杂度是O(n),时间复杂度是O（mn）。
1 public boolean isMatch1(String s, String p) { 2 if (s == null || p == null) { 3 return false; 4 } 5 6 int lens = s.length(); 7 int lenp = p.length(); 8 9 // 创建一个Dp二维数组10 boolean[][] D = new boolean[lens + 1][lenp + 1];11 12 boolean flag = false;13 14 for (int i = 0; i <= lens; i++) {15 flag = false;16 for (int j = 0; j <= lenp; j++) {17 // both is empty.18 if (i == 0 && j == 0) {19 D[i][j] = true;20 flag = true;21 continue;22 }23 24 // if P is empty, s is not empty, it is false.25 if (j == 0) {26 D[i][j] = false;27 continue;28 }29 30 // if S is empty, P is not empty31 if (i == 0) {32 D[i][j] = D[i][j - 1] && p.charAt(j - 1) == ‘*‘;33 } else {34 D[i][j] = (matchChar(s.charAt(i - 1), p.charAt(j - 1)) && D[i - 1][j - 1])35 || (p.charAt(j - 1) == ‘*‘ && (D[i][j - 1] || D[i - 1][j])); 36 }37 38 if (D[i][j]) {39 flag = true;40 }41 42 // Greedy. 在此即可以退出，因为* 可以匹配余下的所有的字符串。 43 if (D[i][j] && p.charAt(j - 1) == ‘*‘ && j == lenp) {44 return true;45 }46 }47 48 if (!flag) {49 return false;50 }51 }52 53 return D[lens][lenp];54 }55 56 public static boolean matchChar(char c, char p) {57 return (p == ‘?‘ || p == c);58 }59 }
但是这个算法过不了Leetcode的大数据检查，即使加了几个优化也是如此。
SOLUTION 2:
下面是迭代程序，要熟悉这个思维：记录上一次开始比较的位置，如图：
