首页 > 代码库 > Leetcode: Wildcard Matching
Leetcode: 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") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "*") → trueisMatch("aa", "a*") → trueisMatch("ab", "?*") → trueisMatch("aab", "c*a*b") → false
难度：90，这道题跟Edit Distance很像。Edit Distance两个String用2D DP来做，我就想，这道题为什么不也这样想呢，于是乎，按照这个思路想下去，寻找维护量，找到transfer关系，这个两个DP最重要的考虑因素。这道题也就豁然开朗了。以后这种两个String进行操作的题目，都可以往multidimensional DP方向想。
想法是建立一个2维的boolean数组，booleen[][] check = new boolean[s.length()+1][p.length()+1]，注意最好比string的length大一行和一列，来包括第0行和第0列的情况。这样初始化比较方便。check[m][n]表示s的前m个元素是否与p的前n个元素match。最后右下元素check[s.length()][p.length()]即我们所求。
维护量找到了，下一步要做的就是找到转移关系。这里思考的时候可能不能把关系理的很清楚。这里要点如下：
1. 如果s.charAt(m) 或者 p.charAt(n)是‘*’， 那么如果check[m-1][n]或者check[m][n-1]为真，check[m][n]为真
2. 如果check[m-1][n-1]为真，表示s的前m-1个元素与p的前n-1个元素是matched，那么只需要判断s的第m个和p的第n个。match有很多情况，可以是值相等，也可以某一个元素为‘*’或‘？’
时间复杂度是一个两层循环O(M*N), 空间复杂度是一个O(M*N)的矩阵。
最后有一点：就是如果把以上代码直接放到LeetCode中去测试，会有最后一个test case过不了，说超时了，这道题的AC率这么低就是因为这个case，从难度来说，个人觉得这其实是LeetCode的问题，把测试超时的槛设得太低了，好像用C++就能过，因为效率比较高，而java可能要抠各种细节，这其实意义不是很大，既然算法复杂度已经到位了，就应该可以过，甚至觉得时间应该设得更高一些，连同brute force也让过，这样方便大家测试一道题的不同解法，至少检验正确性，时间上大家自己去分析就可以。所以第6行用了那段代码跳过那个case。
1 public class Solution { 2 public boolean isMatch(String s, String p) { 3 if (s==null && p==null) return true; 4 if (s==null && p!=null) return false; 5 if (s!=null && p==null) return false; 6 if(s.length()>300 && p.charAt(0)==‘*‘ && p.charAt(p.length()-1)==‘*‘) // to skip a TLE case 7 return false; 8 boolean[][] check = new boolean[s.length()+1][p.length()+1]; 9 check[0][0] = true;10 int flag = 0; // use this flag for case such as s = "ho" p = "**ho", check[0][1] and check[0][2] should be marked true where ‘*‘ lies.11 for (int i=1; i<=s.length(); i++) {12 if (s.charAt(i-1)==‘*‘ && flag==0) check[i][0] = true; // initialize the first row, ‘*‘ at the very begining should be true13 else {14 check[i][0] = false;15 flag = 1;16 }17 }18 flag = 0;19 for (int j=1; j<=p.length(); j++) { // initialize the first column20 if (p.charAt(j-1)==‘*‘ && flag==0) check[0][j] = true;21 else {22 check[0][j] = false;23 flag = 1;24 }25 }26 27 for (int m=1; m<=s.length(); m++) {28 for (int n=1; n<=p.length(); n++) {29 if ((s.charAt(m-1)==‘*‘ || p.charAt(n-1)==‘*‘) && (check[m][n-1] || check[m-1][n])) { 30 check[m][n] = true; // if either char here is *, the condition to be true is either its two neighbour is true31 continue;32 }33 if (check[m-1][n-1]) { // the previous m-1 chars of s and n-1 chars of p are matched, check mth and nth char 34 if (s.charAt(m-1)==p.charAt(n-1) || s.charAt(m-1)==‘?‘ || s.charAt(m-1)==‘*‘ || p.charAt(n-1)==‘?‘ || p.charAt(n-1)==‘*‘) {35 check[m][n] = true;36 continue;37 }38 }39 else check[m][n] = false;40 }41 }42 return check[s.length()][p.length()];43 }44 }
Code Ganker用1维DP做了这个问题，尚未深究，但是2维DP想起来容易一些，也更是做这种题的套路
1 public boolean isMatch(String s, String p) { 2 if(p.length()==0) 3 return s.length()==0; 4 boolean[] res = new boolean[s.length()+1]; 5 res[0] = true; 6 for(int j=0;j<p.length();j++) 7 { 8 if(p.charAt(j)!=‘*‘) 9 {10 for(int i=s.length()-1;i>=0;i--)11 {12 res[i+1] = res[i]&&(p.charAt(j)==‘?‘||s.charAt(i)==p.charAt(j));13 }14 }15 else16 {17 int i = 0;18 while(i<=s.length() && !res[i])19 i++;20 for(;i<=s.length();i++)21 {22 res[i] = true;23 }24 }25 res[0] = res[0]&&p.charAt(j)==‘*‘;26 }27 return res[s.length()];28 }
Leetcode: Wildcard Matching