|
| 1 | +#[Wildcard Matching][title] |
| 2 | + |
| 3 | +##Description |
| 4 | + |
| 5 | +Implement wildcard pattern matching with support for`'?'` and`'*'`. |
| 6 | + |
| 7 | +``` |
| 8 | +'?' Matches any single character. |
| 9 | +'*' Matches any sequence of characters (including the empty sequence). |
| 10 | +
|
| 11 | +The matching should cover the entire input string (not partial). |
| 12 | +
|
| 13 | +The function prototype should be: |
| 14 | +bool isMatch(const char *s, const char *p) |
| 15 | +
|
| 16 | +Some examples: |
| 17 | +isMatch("aa","a") → false |
| 18 | +isMatch("aa","aa") → true |
| 19 | +isMatch("aaa","aa") → false |
| 20 | +isMatch("aa", "*") → true |
| 21 | +isMatch("aa", "a*") → true |
| 22 | +isMatch("ab", "?*") → true |
| 23 | +isMatch("aab", "c*a*b") → false |
| 24 | +``` |
| 25 | + |
| 26 | +**Tags:** String, Dynamic Programming, Backtracking, Greedy |
| 27 | + |
| 28 | + |
| 29 | +##思路0 |
| 30 | + |
| 31 | +题意是让让你从判断`s`字符串是否通配符匹配于`p`，这道题和[Regular Expression Matching][010]很是相似，区别在于`*`，正则匹配的`*`不能单独存在，前面必须具有一个字符，其意义是表明前面的这个字符个数可以是任意个数，包括0个；而通配符的`*`是可以随意出现的，跟前面字符没有任何关系，其作用是可以表示任意字符串。在此我们可以利用*贪心算法*来解决这个问题，需要两个额外指针`p`和`match`来分别记录最后一个`*`的位置和`*`匹配到`s`字符串的位置，其贪心体现在如果遇到`*`，那就尽可能取匹配后方的内容，如果匹配失败，那就回到上一个遇到`*`的位置来继续贪心。 |
| 32 | + |
| 33 | +```java |
| 34 | +classSolution { |
| 35 | +publicbooleanisMatch(Strings,Stringp) { |
| 36 | +if (p.length()==0)return s.length()==0; |
| 37 | +int si=0, pi=0, match=0, star=-1; |
| 38 | +int sl= s.length(), pl= p.length(); |
| 39 | +char[] sc= s.toCharArray(), pc= p.toCharArray(); |
| 40 | +while (si< sl) { |
| 41 | +if (pi< pl&& (pc[pi]== sc[si]|| pc[pi]=='?')) { |
| 42 | + si++; |
| 43 | + pi++; |
| 44 | + }elseif (pi< pl&& pc[pi]=='*') { |
| 45 | + star= pi++; |
| 46 | + match= si; |
| 47 | + }elseif (star!=-1) { |
| 48 | + si=++match; |
| 49 | + pi= star+1; |
| 50 | + }elsereturnfalse; |
| 51 | + } |
| 52 | +while (pi< pl&& pc[pi]=='*') pi++; |
| 53 | +return pi== pl; |
| 54 | + } |
| 55 | +} |
| 56 | +``` |
| 57 | + |
| 58 | + |
| 59 | +##思路1 |
| 60 | + |
| 61 | +另一种思路就是动态规划了，我们定义`dp[i][j]`的真假来表示`s[0..i)`是否匹配`p[0..j)`，其状态转移方程如下所示： |
| 62 | +* 如果`p[j - 1] != '*'`，`P[i][j] = P[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '?');` |
| 63 | +* 如果`p[j - 1] == '*'`，`P[i][j] = P[i][j - 1] || P[i - 1][j]` |
| 64 | + |
| 65 | +```java |
| 66 | +classSolution { |
| 67 | +publicbooleanisMatch(Strings,Stringp) { |
| 68 | +if (p.length()==0)return s.length()==0; |
| 69 | +int sl= s.length(), pl= p.length(); |
| 70 | +boolean[][] dp=newboolean[sl+1][pl+1]; |
| 71 | +char[] sc= s.toCharArray(), pc= p.toCharArray(); |
| 72 | + dp[0][0]=true; |
| 73 | +for (int i=1; i<= pl;++i) { |
| 74 | +if (pc[i-1]=='*') dp[0][i]= dp[0][i-1]; |
| 75 | + } |
| 76 | +for (int i=1; i<= sl;++i) { |
| 77 | +for (int j=1; j<= pl;++j) { |
| 78 | +if (pc[j-1]!='*') { |
| 79 | + dp[i][j]= dp[i-1][j-1]&& (sc[i-1]== pc[j-1]|| pc[j-1]=='?'); |
| 80 | + }else { |
| 81 | + dp[i][j]= dp[i][j-1]|| dp[i-1][j]; |
| 82 | + } |
| 83 | + } |
| 84 | + } |
| 85 | +return dp[sl][pl]; |
| 86 | + } |
| 87 | +} |
| 88 | +``` |
| 89 | + |
| 90 | + |
| 91 | +##结语 |
| 92 | + |
| 93 | +如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：[awesome-java-leetcode][ajl] |
| 94 | + |
| 95 | + |
| 96 | + |
| 97 | +[010]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/010/README.md |
| 98 | +[title]:https://leetcode.com/problems/wildcard-matching |
| 99 | +[ajl]:https://github.com/Blankj/awesome-java-leetcode |