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") → 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
想法是建立一个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-1) 或者 p.charAt(n-1)是‘*’， 那么如果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)的矩阵。
第二遍做法：Time Complexity O(N^2), Space can be optimize to O(N)
1 public class Solution { 2 public boolean isMatch(String s, String p) { 3 int m = s.length(), n = p.length(); 4 char[] ws = s.toCharArray(); 5 char[] wp = p.toCharArray(); 6 boolean[][] dp = new boolean[m+1][n+1]; 7 dp[0][0] = true; 8 for (int j = 1; j <= n; j++) 9 dp[0][j] = dp[0][j-1] && wp[j-1] == '*'; 10 for (int i = 1; i <= m; i++) 11 dp[i][0] = false; 12 for (int i = 1; i <= m; i++) { 13 for (int j = 1; j <= n; j++) { 14 if (wp[j-1] == '?' || ws[i-1] == wp[j-1]) 15 dp[i][j] = dp[i-1][j-1]; 16 else if (wp[j-1] == '*') 17 dp[i][j] = dp[i-1][j] || dp[i][j-1]; 18 } 19 } 20 return dp[m][n]; 21 } 22 }
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 else 16 { 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 }
backtracking做法：参 https://discuss.leetcode.com/topic/3040/linear-runtime-and-constant-space-solution
We can use two pointers s and p to record the current place for matching
This algorithm iterates at most length(string) + length(pattern) times, for each iteration, at least one pointer advance one step.
1 boolean comparison(String str, String pattern) { 2 int s = 0, p = 0, match = 0, starIdx = -1; 3 while (s < str.length()){ 4 // advancing both pointers 5 if (p < pattern.length() && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){ 6 s++; 7 p++; 8 } 9 // * found, only advancing pattern pointer 10 else if (p < pattern.length() && pattern.charAt(p) == '*'){ 11 starIdx = p; 12 match = s; 13 p++; 14 } 15 // last pattern pointer was *, advancing string pointer 16 else if (starIdx != -1){ 17 p = starIdx + 1; 18 match++; 19 s = match; 20 } 21 //current pattern pointer is not star, last patter pointer was not * 22 //characters do not match 23 else return false; 24 } 25 26 //check for remaining characters in pattern 27 while (p < pattern.length() && pattern.charAt(p) == '*') 28 p++; 29 30 return p == pattern.length(); 31 }