LeetCode 44 - Wildcard Matching


Related: LeetCode 10 - Regular Expression Matching
Wildcard Matching, Leetcode 解题笔记 | Simple & Stupid
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

https://www.cnblogs.com/grandyang/p/4401196.html
这道题也能用动态规划Dynamic Programming来解，写法跟之前那道题 Regular Expression Matching 很像，但是还是不一样。外卡匹配和正则匹配最大的区别就是在星号的使用规则上，对于正则匹配来说，星号不能单独存在，前面必须要有一个字符，而星号存在的意义就是表明前面这个字符的个数可以是任意个，包括0个，那么就是说即使前面这个字符并没有在s中出现过也无所谓，只要后面的能匹配上就可以了。而外卡匹配就不是这样的，外卡匹配中的星号跟前面的字符没有半毛钱关系，如果前面的字符没有匹配上，那么直接返回false了，根本不用管星号。而星号存在的作用是可以表示任意的字符串，当然只是当匹配字符串缺少一些字符的时候起作用，当匹配字符串p包含目标字符串s中没有的字符时，将无法成功匹配。
对于这种玩字符串的题目，动态规划Dynamic Programming是一大神器，因为字符串跟其子串之间的关系十分密切，正好适合DP这种靠推导状态转移方程的特性。那么先来定义dp数组吧，我们使用一个二维dp数组，其中 dp[i][j] 表示 s中前i个字符组成的子串和p中前j个字符组成的子串是否能匹配。大小初始化为 (m+1) x (n+1)，加1的原因是要包含dp[0][0] 的情况，因为若s和p都为空的话，也应该返回true，所以也要初始化 dp[0][0] 为true。还需要提前处理的一种情况是，当s为空，p为连续的星号时的情况。由于星号是可以代表空串的，所以只要s为空，那么连续的星号的位置都应该为true，所以我们现将连续星号的位置都赋为true。然后就是推导一般的状态转移方程了，如何更新 dp[i][j]，首先处理比较tricky的情况，若p中第j个字符是星号，由于星号可以匹配空串，所以如果p中的前j-1个字符跟s中前i个字符匹配成功了（dp[i][j-1] 为true）的话，那么 dp[i][j] 也能为true。或者若 p中的前j个字符跟s中的前i-1个字符匹配成功了（dp[i-1][j] 为true）的话，那么 dp[i][j] 也能为true（因为星号可以匹配任意字符串，再多加一个任意字符也没问题）。若p中的第j个字符不是星号，对于一般情况，我们假设已经知道了s中前i-1个字符和p中前j-1个字符的匹配情况（即 dp[i-1][j-1] ），那么现在只需要匹配s中的第i个字符跟p中的第j个字符，若二者相等（s[i-1] == p[j-1]），或者p中的第j个字符是问号（p[j-1] == '?'），再与上 dp[i-1][j-1] 的值，就可以更新 dp[i][j] 了
X.
X. Two pointers
http://happycoding2010.blogspot.com/2015/09/leetcode-43-wildcard-matching.html
https://yujia.io/blog/2015/11/15/LeetCode-44-Wildcard-Matching/
In this specific problem, the DP algorithm doesn’t use the fact that if we meet another '*', then the last '*' we meet can be ignore. I use a Two-Pointer algorithm to get a linear time algorithm.
Set i, j as the index for s and p. They goes from 0,…,n−1 and 0,…,m−1 respectively. Let lastp be the index before which we met '*'. And lasts be the index of the s which we try to match with p[lastp]. At first we initialize lastp and lasts to be −1. Also we set i=0 and j=0.
As long as i < n, we run the loop. There are three possible cases:
  • s[i] == p[j] or p[j] == '?'. Then we match these two character and add i and j by 1.
  • p[j] == '*'. Then set lastp = j+1 and lasts = i. (Because we can match '*' with empty)
  • lastp != -1. If we are in this case, then it means we need to rematch the previous '*'. Set lasts+=1and j=lastp.
When the loop terminate, we need to check the rest element in p[j:end]. If all elements in p[j:end] is '*', then it should be true. Otherwise, it cannot match. Why? Because in this algorithm, once we met a '*' in p, we ignore the previous '*' and start using it to match the remaining string. It’s kind of greedy. If there is a non '*'left in p[j:end], then it means we cannot find a way to match p with s.
Since in each times of loop, we at least add either i or j by one.
So the overall time complexity will be O(n+m). It’s much better than the DP algorithm above.
Space complexity is O(n+m) which is the same as the input.
        bool isMatch(string s, string p) {
            auto n = s.size(), m = p.size();
            int j = 0;
            for(int i = 0, lastp = -1, lasts = -1; i != n;){
                if ((s[i] == p[j]) || (p[j] == '?')){
                    i++; j++;
                }else if (p[j] == '*'){
                    j++;
                    lastp = j;
                    lasts = i;
                }else if (lastp != -1){
                    j = lastp;
                    i = ++lasts;
                }else
                    return false;
            }
            for (; (j < m) && (p[j] == '*'); j++);
            return (j == m);
        }

http://www.programcreek.com/2014/06/leetcode-wildcard-matching-java/
public boolean isMatch(String s, String p) {
 int i = 0;
 int j = 0;
 int starIndex = -1;
 int iIndex = -1;
 
 while (i < s.length()) {
  if (j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
   ++i;
   ++j;
  } else if (j < p.length() && p.charAt(j) == '*') {
   starIndex = j;  
   iIndex = i;
   j++;
  } else if (starIndex != -1) {
   j = starIndex + 1;
   i = iIndex+1;
   iIndex++;
  } else {
   return false;
  }
 }
 
 while (j < p.length() && p.charAt(j) == '*') {
  ++j;
 }
 
 return j == p.length();
}
https://leetcode.com/discuss/10133/linear-runtime-and-constant-space-solution
The basic idea is to have one pointer for the string and one pointer for the pattern. This algorithm iterates at most length(string) + length(pattern) times, for each iteration, at least one pointer advance one step.
not linear time really, but the code is elegant and can pass large set test cases
boolean comparison(String str, String pattern) {
        int s = 0, p = 0, match = 0, starIdx = -1;            
        while (s < str.length()){
            // advancing both pointers
            if (p < pattern.length()  && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){
                s++;
                p++;
            }
            // * found, only advancing pattern pointer
            else if (p < pattern.length() && pattern.charAt(p) == '*'){
                starIdx = p;
                match = s;
                p++;
            }
           // last pattern pointer was *, advancing string pointer
            else if (starIdx != -1){
                p = starIdx + 1;
                match++;
                s = match;
            }
           //current pattern pointer is not star, last patter pointer was not *
          //characters do not match
            else return false;
        }
        
        //check for remaining characters in pattern
        while (p < pattern.length() && pattern.charAt(p) == '*')
            p++;
        
        return p == pattern.length();
}
For each element in s
If *s==*p or *p == ? which means this is a match, then goes to next element s++ p++.
If p=='*', this is also a match, but one or many chars may be available, so let us save this *'s position and the matched s position.
If not match, then we check if there is a * previously showed up,
       if there is no *,  return false;
       if there is an *,  we set current p to the next element of *, and set current s to the next saved s position.

e.g.

abed
?b*d**

a=?, go on, b=b, go on,
e=*, save * position star=3, save s position ss = 3, p++
e!=d,  check if there was a *, yes, ss++, s=ss; p=star+1
d=d, go on, meet the end.
check the rest element in p, if all are *, true, else false;

Note that in char array, the last is NOT NULL, to check the end, use  "*p"  or "*p=='\0'".
boolean comparison(String str, String pattern) { int s = 0, p = 0, match = 0, starIdx = -1; while (s < str.length()){ // advancing both pointers if (p < pattern.length() && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){ s++; p++; } // * found, only advancing pattern pointer else if (p < pattern.length() && pattern.charAt(p) == '*'){ starIdx = p; match = s; p++; } // last pattern pointer was *, advancing string pointer else if (starIdx != -1){ p = starIdx + 1; match++; s = match; } //current pattern pointer is not star, last patter pointer was not * //characters do not match else return false; } //check for remaining characters in pattern while (p < pattern.length() && pattern.charAt(p) == '*') p++; return p == pattern.length(); }

if (*p=='*'){star=p++; ss=s;continue;} if (star){ p = star+1; s=++ss;continue;} //pointer s will go back , so not O(n).
For example, s = "aaaaaaaaaaaaaaaab", p = "a*aaaaaaab", it's O(mn)
https://discuss.leetcode.com/topic/3040/linear-runtime-and-constant-space-solution
The basic idea is to have one pointer for the string and one pointer for the pattern. This algorithm iterates at most length(string) + length(pattern) times, for each iteration, at least one pointer advance one step.
not linear time really, but the code is elegant and can pass large set test cases

I agree with dtcxzch. The complexity of the algorithm is O(p*s), where p and s are the lengths of the pattern and input strings. An example of such a worst-case input is:
input: bbbbbbbbbbbb
pattern: *bbbb
boolean comparison(String str, String pattern) {
        int s = 0, p = 0, match = 0, starIdx = -1;            
        while (s < str.length()){
            // advancing both pointers
            if (p < pattern.length()  && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){
                s++;
                p++;
            }
            // * found, only advancing pattern pointer
            else if (p < pattern.length() && pattern.charAt(p) == '*'){
                starIdx = p;
                match = s;
                p++;
            }
           // last pattern pointer was *, advancing string pointer
            else if (starIdx != -1){
                p = starIdx + 1;
                match++;
                s = match;
            }
           //current pattern pointer is not star, last patter pointer was not *
          //characters do not match
            else return false;
        }
        
        //check for remaining characters in pattern
        while (p < pattern.length() && pattern.charAt(p) == '*')
            p++;
        
        return p == pattern.length();
}
X. DP
public boolean isMatch(String s, String p) {
    int count = 0;
    for (char c : p.toCharArray()) {
        if (c == '*')
            count++;
    }
    if (p.length() - count > s.length())
        return false;
    boolean[][] dp = new boolean[p.length() + 1][s.length() + 1];
    dp[0][0] = true;
    for (int j = 1; j <= p.length(); j++) {
        char pattern = p.charAt(j - 1);
        dp[j][0] = dp[j - 1][0] && pattern == '*';
        for (int i = 1; i <= s.length(); i++) {
            char letter = s.charAt(i - 1);
            if (pattern != '*') {
                dp[j][i] = dp[j - 1][i - 1] && (pattern == '?' || pattern == letter);
            } else
                dp[j][i] = dp[j][i - 1] || dp[j - 1][i];
        }
    }
    return dp[p.length()][s.length()];
}

The key of the problem is to understand the '*', which is able to match ANY sequence of characters. e.g. isMatch(abcd, *) -> true. Note that * does not require the same character in the sequence, as was required by the regular expression matching. 

We use DP to solve this problem. 
  -- Define dp[s.length() + 1][p.length() + 1], where dp[i[j] means the first i characters in string s matches the first characters of string p. 
  -- Initialization: dp[0][0] = true; 
                          dp[i][0] = false;
                          dp[0][j] = dp [0][j - 1] IFF p.charAt(j - 1) == '*'

-- Transit function: 
        -- If p.charAt(j - 1) != '*', then dp[i][j] = dp[i - 1][j - 1] IFF s.charAt(i) == p.charAt(j) || p.charAt(j) == '?'
        -- If p.charAt(j - 1) == '*', then 
             -- dp[i][j] = dp[i - 1][j - 1] || // Match 1 character
                           = dp[i][j - 1] || // Match 0 character
                           = dp[i - 1][j] // Match any sequence of characters 

-- Return dp[s.length()][p.length()].
    public boolean isMatch(String s, String p) {
        if (p == null || p.length() == 0) {
            return s == null || s.length() == 0;
        }
         
        int rows = s.length();
        int cols = p.length();
         
        boolean[][] dp = new boolean[rows + 1][cols + 1];
         
        dp[0][0] = true;
        for (int j = 1; j <= cols; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 1];
            }
        }
         
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (p.charAt(j - 1) != '*') {
                    if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                } else {
                    dp[i][j] = dp[i - 1][j - 1] || dp[i][j - 1] || dp[i - 1][j];
                }
            }
        }
         
        return dp[s.length()][p.length()];
    }
p[j-1] == s[i-1] || p[j-1] == '?'：dp[i][j] = dp[i-1][j-1]
p[j-1] == '*'：
1. 匹配0个字符：dp[i][j] = dp[i][j-1]
2. 匹配1个字符：dp[i][j] = dp[i-1][j-1]
3. 匹配多个字符：dp[i][j] = dp[i-1][j]
先用二维数组写，发现会Memory Limit Exceeded

https://discuss.leetcode.com/topic/10794/my-java-dp-solution


At first I cannot pass the the long 'aaa...' test case. Then I add more check and pass it.
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (p.charAt(i) == '*') count++;
        }
        if (count==0 && m != n) return false;
        else if (n - count > m) return false;
        
        boolean[] match = new boolean[m+1];
        match[0] = true;
        for (int i = 0; i < m; i++) {
            match[i+1] = false;
        }
        for (int i = 0; i < n; i++) {
            if (p.charAt(i) == '*') {
                for (int j = 0; j < m; j++) {
                    match[j+1] = match[j] || match[j+1]; 
                }
            } else {
                for (int j = m-1; j >= 0; j--) {
                    match[j+1] = (p.charAt(i) == '?' || p.charAt(i) == s.charAt(j)) && match[j];
                }
                match[0] = false;
            }
        }
        return match[m];
    }
X. DP backward
https://blog.csdn.net/aximi/article/details/83898167

https://leetcode.com/problems/wildcard-matching/discuss/17812/My-java-DP-solution-using-2D-table
    public boolean isMatch(String s, String p) {
        boolean[][] match=new boolean[s.length()+1][p.length()+1];
        match[s.length()][p.length()]=true;
        for(int i=p.length()-1;i>=0;i--){
            if(p.charAt(i)!='*')
                break;
            else
                match[s.length()][i]=true;
        }
        for(int i=s.length()-1;i>=0;i--){
            for(int j=p.length()-1;j>=0;j--){
                if(s.charAt(i)==p.charAt(j)||p.charAt(j)=='?')
                        match[i][j]=match[i+1][j+1];
                else if(p.charAt(j)=='*')
                        match[i][j]=match[i+1][j]||match[i][j+1];
                else
                    match[i][j]=false;
            }
        }
        return match[0][0];
    }
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        char[] ws = s.toCharArray();
        char[] wp = p.toCharArray();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for (int j = 1; j <= n; j++)
            dp[0][j] = dp[0][j-1] && wp[j-1] == '*';
        for (int i = 1; i <= m; i++)
            dp[i][0] = false;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
             if (wp[j-1] == '?' || ws[i-1] == wp[j-1])
              dp[i][j] = dp[i-1][j-1];
             else if (wp[j-1] == '*')
              dp[i][j] = dp[i-1][j] || dp[i][j-1];
            }
        }
        return dp[m][n];
    }

X. O(n) space
https://leetcode.com/problems/wildcard-matching/discuss/17871/O(n)-space-DP-using-two-1-d-array-to-rotate.
public boolean isMatch(String s, String p) {
        if(p.isEmpty())
            return s.isEmpty();
            
        /*init array*/
        boolean[] d = new boolean[s.length() +1];
        boolean[] next = new boolean[s.length() +1];
        
        d[0] = true;
        for(char c: p.toCharArray()){
            next[0] = c == '*' ? d[0] : false; // init first element
            
            for(int i = 1; i <= s.length(); i ++){
                if(c == '?'){
                    next[i] = d[i-1];
                }
                else if (c == '*'){
                    next[i] = d[i] || next[i-1];
                }
                else { // normal char
                    next[i] = d[i-1] && (c == s.charAt(i-1));
                }
            }
            
            // rotate forward, dont have to clean up. 
            boolean[] tmp = d;
            d = next;
            next = tmp;
        }
        
        return d[s.length()];
    }
https://leetcode.com/problems/wildcard-matching/discuss/17893/Java-DP-O(mn)-time-O(n)-space-with-rolling-array-trick
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] match = new boolean[2][n + 1];
        match[0][0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (j == 0) { // initialized first column
                    match[i % 2][j] = i == 0;
                    continue;
                }
                if (p.charAt(j - 1) == '*') {
                    match[i % 2][j] = (i > 0 && match[(i - 1) % 2][j]) || match[i % 2][j - 1];
                } else {
                    match[i % 2][j] = i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') && match[(i - 1) % 2][j - 1];
                }
                
            }
        }
        return match[m % 2][n];
    }

然后用一维滚动数组改写，发现会Time Limit Exceeded
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int m = strlen(s), n = strlen(p);
        vector<bool> dp(m+1, false);
        for(int i=0; i<m; i++) {
            bool diag = dp[0];
            dp[0] = i==0 ? true : false;
            for(int j=1; j<n; j++) {
                int temp = dp[j];
                if(p[j-1]==s[i-1] || p[j-1]=='?') 
                    dp[j] = i>0 && diag;
                else if(p[j-1]=='*') 
                    dp[j] = dp[j-1] || (i>0 && (diag || dp[j]));
                diag = temp;
            }
        }
        return dp[n];
    }
};
http://happycoding2010.blogspot.com/2015/09/leetcode-43-wildcard-matching.html
   public boolean isMatch(String s, String p) {  
     int m=s.length();  
     int n=p.length();  
     boolean[] dp=new boolean[n+1];  
     for (int i=0; i<=m; i++) {  
       boolean pre=false;  
       for (int j=0; j<=n; j++) {  
         boolean temp=dp[j];  
         if (i==0) {  
           if (j==0) dp[j]=true;  
           else if (p.charAt(j-1)=='*') dp[j]=dp[j-1];  
           else dp[j]=false;  
         }  
         else if (j==0) dp[j]=false;  
         else if (p.charAt(j-1)=='?') dp[j]=pre;  
         else if (p.charAt(j-1)=='*') dp[j]=dp[j] || dp[j-1];  
         else if (s.charAt(i-1)==p.charAt(j-1)) dp[j]=pre;  
         else dp[j]=false;  
         pre=temp;  
       }  
     }  
     return dp[n];  
   }
TODO:https://discuss.leetcode.com/topic/11392/my-java-dp-solution
public boolean isMatch(String s, String p) {
    if (p.replace("*", "").length() > s.length())
        return false;
 boolean[] d = new boolean[s.length() + 1];
 d[0] = true;
 for (int i = 1; i < s.length(); ++i) {
  d[i] = false;
 }
 for (int i = 1; i <= p.length(); ++i) {
  char pchar = p.charAt(i - 1);
  if (pchar == '*') {
   for (int j = 1; j <= s.length(); ++j) {
    d[j] = d[j - 1] || d[j];
   }
  }
  else {
   for (int j = s.length(); j >= 1; --j) {
    d[j] = d[j - 1] && (pchar == '?' || pchar == s.charAt(j - 1));
   }
  }
  d[0] = d[0] && pchar == '*';
 }
 return d[s.length()];
}
X. Space Optimization:
http://likesky3.iteye.com/blog/2217581
  1.     // Method1: Time: O(m * n), Space: O(n)，两个一维数组  
  2.     // dp[i][j] : p的前i个字符能否匹配s的前j个字符  
  3.     public boolean isMatch1(String s, String p) {  
  4.         if (p == null || s == null)  
  5.             return false;  
  6.         int lengthS = s.length();  
  7.         int lengthP = p.length();  
  8.         if (lengthS > 300 && p.charAt(0) == '*' && p.charAt(lengthP - 1) == '*')  
  9.             return false;  
  10.         boolean[][] dp = new boolean[2][lengthS + 1];  
  11.         dp[0][0] = true;  
  12.         int lastRow = 1;  
  13.         int currRow = 0;  
  14.         for (int i = 1; i <= lengthP; i++) {  
  15.             lastRow = currRow;  
  16.             currRow = 1 - lastRow;  
  17.             char charP = p.charAt(i - 1);  
  18.             dp[currRow][0] = dp[lastRow][0] && charP == '*';  
  19.             for (int j = 1; j <= lengthS; j++) {  
  20.                 char charS = s.charAt(j - 1);  
  21.                 if (charP == charS || charP == '?') {  
  22.                     dp[currRow][j] = dp[lastRow][j - 1];  
  23.                 } else if(charP == '*'){  
  24.                     dp[currRow][j] = dp[lastRow][j - 1] || dp[lastRow][j] || dp[currRow][j - 1];  
  25.                 } else {  
  26.                     dp[currRow][j] = false;  
  27.                 }  
  28.             }  
  29.         }  
  30.         return dp[currRow][lengthS];  
  31.     }  
  32.       
  33.     // Method2: Time: O(m * n), Space: O(n), 一维数组  
  34.     // dp[j] : p的前i个字符能否匹配s的前j个字符  
  35.     // http://blog.csdn.net/linhuanmars/article/details/21198049  
  36.     public boolean isMatch2(String s, String p) {  
  37.         if (p == null || s == null)  
  38.             return false;  
  39.         int lengthS = s.length();  
  40.         int lengthP = p.length();  
  41.         if (lengthS > 300 && p.charAt(0) == '*' && p.charAt(lengthP - 1) == '*')  
  42.             return false;  
  43.         boolean[] dp = new boolean[lengthS + 1];  
  44.         dp[0] = true;  
  45.         for (int i = 1; i <= lengthP; i++) {  
  46.             char charP = p.charAt(i - 1);  
  47.             if (charP != '*') {  
  48.                 for (int j = lengthS; j >= 1; j--) {  
  49.                     dp[j] = dp[j - 1] && (charP == s.charAt(j - 1) || charP == '?');  
  50.                 }  
  51.             } else {  
  52.                 int j = 0;  
  53.                 while (j <= lengthS && !dp[j])  
  54.                     j++;  
  55.                 while (j <= lengthS) {  
  56.                     dp[j++] = true;  
  57.                 }  
  58.             }  
  59.             dp[0] = dp[0] && charP == '*';  
  60.         }  
  61.         return dp[lengthS];  
  62.     }  

https://discuss.leetcode.com/topic/10794/my-java-dp-solution
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (p.charAt(i) == '*') count++;
        }
        if (count==0 && m != n) return false;
        else if (n - count > m) return false;
        
        boolean[] match = new boolean[m+1];
        match[0] = true;
        for (int i = 0; i < m; i++) {
            match[i+1] = false;
        }
        for (int i = 0; i < n; i++) {
            if (p.charAt(i) == '*') {
                for (int j = 0; j < m; j++) {
                    match[j+1] = match[j] || match[j+1]; 
                }
            } else {
                for (int j = m-1; j >= 0; j--) {
                    match[j+1] = (p.charAt(i) == '?' || p.charAt(i) == s.charAt(j)) && match[j];
                }
                match[0] = false;
            }
        }
        return match[m];
    }

http://blog.csdn.net/linhuanmars/article/details/21198049
public boolean isMatch(String s, String p) {
    if(p.length()==0)
        return s.length()==0;
    boolean[] res = new boolean[s.length()+1];
    res[0] = true;
    for(int j=0;j<p.length();j++)
    {
        if(p.charAt(j)!='*')
        {
            for(int i=s.length()-1;i>=0;i--)
            {
                res[i+1] = res[i]&&(p.charAt(j)=='?'||s.charAt(i)==p.charAt(j));
            }
        }
        else
        {
            int i = 0;
            while(i<=s.length() && !res[i])
                i++;
            for(;i<=s.length();i++)
            {
                res[i] = true;
            }
        }
        res[0] = res[0]&&p.charAt(j)=='*';
    }
    return res[s.length()];
}
http://www.jiuzhang.com/solutions/wildcard-matching/
http://shmilyaw-hotmail-com.iteye.com/blog/2154716
在不考虑"*"的情况下，我们的方法大致结构如下：
  1. boolean isMatch(String s, String p) {  
  2.     int l = 0, r = 0;  
  3.     while(l < s.length() && r < p.length()) {  
  4.         if(s.charAt(l) == p.charAt(r) || p.charAt(r) == '?') {  
  5.             l++;  
  6.             r++  
  7.         } else return false;  
  8.     }  
  9.     if(l < s.length() || r < p.length()) return false;  
  10.     return true;  
  11. }  
１．假设碰到*号时s串的位置是l, p串的位置是r，则将r+1作为*号后续进行比较的起点。
２．从l开始与r+1位置的元素进行比较，如果相同，再按照常规匹配的方式往后面继续比。否则l跳到前面和r+1开始比较那个位置的后面一个。同时p这边的元素也要归位到r+1
　　所以，到了这一步，我们就知道。当遇到*号的时候，先记录一下l所在的位置和r+1所在的位置。每次匹配比较不对了就回退。假设记录l开始比较位置的元素为match。在每次匹配失败后match就要加１，表示下一个开始比较的起点。
３．既然前面匹配的情况讨论了。对于不匹配的情况呢？假设我们碰到一些不匹配的了。如果前面根本就没有*号，这就是正常的字符串比较不匹配的情况，我们直接就返回匹配不成功了。
４．还有一个问题，这算是比较隐蔽一点的情况。因为我们这边是一碰到*号就一直不停的去比较，如果p串中间有多个*号呢？我们可能已经比较到前面s串的结尾了，但是p串后面可能还有一部分字符。这个时候我们也需要进行判断。如果剩下的是*号，则相当于*号匹配了０个元素，否则表示匹配错误。
  1.     public  boolean isMatch(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.     }
基于上述方法来解决这个问题是一种贪婪算法的思路。因为每次碰到一个*号我们会将它记录下来，然后就去和源串进行比较

它的时间复杂度的话会发现这是一个指数级别的.
  1. boolean isMatch(String s, String p, int l, int r) {  
  2.     if(r == p.length()) return l == s.length();  
  3.     if(p.charAt(r) == '*') {  
  4.         while(p.charAt(r) == '*') r++;   // Move the index at p to a non-start char.  
  5.         while(l < s.length()) {  
  6.             if(isMatch(s, p, l, r)) return true; // Find one match, return true.  
  7.             l++; // Try the next one.  
  8.         }  
  9.         return isMatch(s, p, l, r);  
  10.     } else if(l < s.length() && (p.charAt(j) == '?' || s.charAt(l) == p.charAt(r)))  
  11.         return isMatch(s, p, l + 1, r + 1);  
  12.     return false;  
  13. }

假设我们用F(i, j)表示串s[0...i], p[0...j]这两个串分别到i和j位置它们是否匹配的函数。那么，我们可以得到这样的一个递推关系：
F[i, j] = F[i-1, j-1] &&(s[i] == p[j] || p[j] == '?')  (假设此时p[j] != '*')
F[i, j] = or F[i-1, j-1] for i = 0, ... i-1, 如果p[j] = '*'。这里表示我们从前面开始找到一个对应j-1时为true的情况，表示对应i-1的时候s串匹配的位置，则从这个位置后面所有的位置都是true。
 　所以按照前面的思路，我们可以定义一个二维数组boolean[][] dp = new boolean[s.length()][p.length()]

这种实现方式相对来说性能有了很大的提升，它的时间复杂度为o(m * n)。空间的复杂度也是O(m * n)。实际上，我们还可以对代码做进一步的改进。因为空间计算每次只是用到前一次计算的结果，我们可以将空间的复杂度降低到O(m)
  1. boolean isMatch(String s, String p) {  
  2.     if(p.length() == 0) return s.length() == 0;  
  3.     int m = s.length();  
  4.     int n = p.length();  
  5.     boolean[][] dp = new boolean[m + 1][n + 1];  
  6.     dp[0][0] = true;  
  7.     for(int j = 0; j < n; j++) {  
  8.         if(p.charAt(j) != '*') {  
  9.             for(int i = 0; i < m; i++) {  
  10.                 dp[i + 1][j + 1] = dp[i][j] && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?');  
  11.             }  
  12.         } else{  
  13.             int i = 0;  
  14.             while(i < s.length() && !dp[i][j]) i++;  
  15.             for(; i < m; i++) dp[i][j] = true;  
  16.         }  
  17.     }  
  18.     return dp[m][n];  
  19. }  

对于字符串的模糊匹配问题看起来很简单，实际上牵涉到非常复杂的判断条件。
结合不同的场景，最关键的就是要找到它们的递归关系，
然后进行动态规划方法的优化。

  1. boolean isMatch(String s, String p) {  
  2.     if(p.length() == 0) return s.length() == 0;  
  3.     int m = s.length();  
  4.     int n = p.length();  
  5.     boolean[][] dp = new boolean[m + 1][n + 1];  
  6.     dp[0][0] = true;  
  7.     for(int j = 0; j < n; j++) {  
  8.         if(p.charAt(j) != '*') {  
  9.             for(int i = 0; i < m; i++) {  
  10.                 dp[i + 1][j + 1] = dp[i][j] && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?');  
  11.             }  
  12.         } else{  
  13.             int i = 0;  
  14.             while(i < s.length() && !dp[i][j]) i++;  
  15.             for(; i < m; i++) dp[i][j] = true;  
  16.         }  
  17.     }  
  18.     return dp[m][n];  
  19. } 

public boolean isMatch(String s, String p) {
        int i = 0;
        int j = 0;
        int star = -1;
        int mark = -1;
        while (i < s.length()) {
            if (j < p.length()
                    && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
                ++i;
                ++j;
            } else if (j < p.length() && p.charAt(j) == '*') {
                star = j;
                j++;
                mark = i;
           //这一步是关键，匹配s中当前字符与p中‘＊’后面的字符，如果匹配，则在第一个if中处理，如果不匹配，则继续比较s中的下一个字符。
            } else if (star != -1) {
                j = star + 1;
                i = ++mark;
            } else {
                return false;
            }
        }
       //最后在此处处理多余的‘＊’，因为多个‘＊’和一个‘＊’意义相同。
        while (j < p.length() && p.charAt(j) == '*') {
            ++j;
        }
        return j == p.length();
    }

    bool isMatch(const char *s, const char *p) {
        char cs = *s;
        char cp = *p;
        if(cp == '\0') {
            return cs == cp;
        } else if (cp == '?') {
            if (cs == '\0') return false;
            return isMatch(s + 1,p + 1);
        } else if (cp == '*') {
            const char *st = s;
            for(; *st != '\0'; ++st) {
                if (isMatch(st, p+1)) return true;
            }
            return isMatch(st,p+1);
        } else if (cp != cs)
            return false;
        return isMatch(s + 1,p + 1);
    }

http://zjalgorithm.blogspot.com/2014/11/leetcode-java-wildcard-matching.html
Recursive Version:
public static boolean isMatch(String s, String p) {
    // base
    if(s.length()==0 ) {
        if(p.length()==0) return true;
        for(int i=0; i<p.length(); i++) { // for consecutive '*'
         if(p.charAt(i) != '*') return false;
        }
        return true; // only all * match empty
    }
    if(p.length() == 0) return false;
    if(p.charAt(0) == '?' || p.charAt(0) == s.charAt(0)) {
        return isMatch(s.substring(1), p.substring(1));
    }
    if(p.charAt(0) == '*') {
     int star = 0; // eliminate consecutive '*'
     while(star+1 < p.length() && p.charAt(star+1) == '*') { // !!! star+1 < p.length() is must
      star++;
     }
        return isMatch(s, p.substring(star+1)) || isMatch(s.substring(1), p.substring(star));
    }
    return false;
}
http://vialgorithms.blogspot.com/2013/11/wildcard-matching.html
http://www.cnblogs.com/yuzhangcmu/p/4116153.html
动态规划：输入两个字符串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）。   
http://codeganker.blogspot.com/2014/03/wildcard-matching-leetcode.html
DP: SPace:O(n)(1)p[j]不是'*'。情况比较简单，只要判断如果当前s的i和p的j上的字符一样（如果有p在j上的字符是'?'，也是相同），并且res[i]==true，则更新res[i+1]为true，否则res[i+1]=false;  
    (2)p[j]是'*'。因为'*'可以匹配任意字符串，所以在前面的res[i]只要有true，那么剩下的          res[i+1], res[i+2],...,res[s.length()]就都是true了。
算法的时间复杂度因为是两层循环，所以是O(m*n), 而空间复杂度只用一个一维数组，所以是O(n)
public boolean isMatch(String s, String p) {
    if(p.length()==0)
        return s.length()==0;
    boolean[] res = new boolean[s.length()+1];
    res[0] = true;
    for(int j=0;j<p.length();j++)
    {
        if(p.charAt(j)!='*')
        {
            for(int i=s.length()-1;i>=0;i--)
            {
                res[i+1] = res[i]&&(p.charAt(j)=='?'||s.charAt(i)==p.charAt(j));
            }
        }
        else
        {
            int i = 0;
            while(i<=s.length() && !res[i])
                i++;
            for(;i<=s.length();i++)
            {
                res[i] = true;
            }
        }
        res[0] = res[0]&&p.charAt(j)=='*';
    }
    return res[s.length()];
}

X. DFS

其实这道题也可以使用递归来做，因为子串或者子数组这种形式，天然适合利用递归来做。但是愣了吧唧的递归跟暴力搜索并没有啥太大的区别，很容易被OJ毙掉，比如评论区六楼的那个naive的递归，其实完全是按照题目要求来的。首先判断s串，若为空，那么再看p串，若p为空，则为true，或者跳过星号，继续调用递归。若s串不为空，且p串为空，则直接false。若s串和p串均不为空，那么进行第一个字符的匹配，若相等，或者p[0]是问号，则跳过首字符，对后面的子串调用递归。若p[0] 是星号，那么先尝试跳过s串的首字符，调用递归，若递归返回true，则当前返回true。否则尝试跳过p串的首字符，调用递归，若递归返回true，则当前返回true。但是很不幸，内存超出限制了MLE，那么博主做了个简单的优化，跳过了连续的星号，参见评论区七楼的代码，但是这次时间超出了限制TLE。博主想是不是取子串substr()操作太费时间，且调用递归的适合s串和p串又分别建立了副本，才导致的TLE。于是想着用坐标变量来代替取子串，并且递归函数调用的s串和p串都加上引用，代码参见评论区八楼，但尼玛还是跪了，OJ大佬，刀下留人啊。最后还是在论坛上找到了一个使用了神奇的剪枝的方法，这种解法的递归函数返回类型不是bool型，而是整型，有三种不同的状态，返回0表示匹配到了s串的末尾，但是未匹配成功；返回1表示未匹配到s串的末尾就失败了；返回2表示成功匹配。那么只有返回值大于1，才表示成功匹配。至于为何失败的情况要分类，就是为了进行剪枝。在递归函数中，若s串和p串都匹配完成了，返回状态2。若s串匹配完成了，但p串但当前字符不是星号，返回状态0。若s串未匹配完，p串匹配完了，返回状态1。若s串和p串均为匹配完，且当前字符成功匹配的话，对下一个位置调用递归。否则若p串当前字符是星号，那么我们首先跳过连续的星号。然后我们分别让星号匹配空串，一个字符，两个字符，....，直到匹配完整个s串，对每种情况分别调用递归函数，接下来就是最大的亮点了，也是最有用的剪枝，当前返回值为状态0或者2的时候，返回，否则继续遍历。如果我们仅仅是状态2的时候才返回，就像评论区八楼的代码，会有大量的重复计算，因为当返回值为状态0的时候，已经没有继续循环下去的必要了，非常重要的一刀剪枝，参见代码如下：
    bool isMatch(string s, string p) {
        return helper(s, p, 0, 0) > 1;
    }
    int helper(string& s, string& p, int i, int j) {
        if (i == s.size() && j == p.size()) return 2;
        if (i == s.size() && p[j] != '*') return 0;
        if (j == p.size()) return 1;
        if (s[i] == p[j] || p[j] == '?') {
            return helper(s, p, i + 1, j + 1);
        }
        if (p[j] == '*') {
            if (j + 1 < p.size() && p[j + 1] == '*') {
                return helper(s, p, i, j + 1);
            }
            for (int k = 0; k <= (int)s.size() - i; ++k) {
                int res = helper(s, p, i + k, j + 1);
                if (res == 0 || res == 2) return res;
            }
        }
        return 1;
    }

http://www.voidcn.com/article/p-ehnxhspt-gt.html
bool isMatch(string s, string p) {

        if(p.empty()){
            return s.empty();
        }

        if(p[0]=='*'){
            int i=1;
            while(p[i]=='*'){
                i++;
            }
            p = p.substr(i);

            if(p==""){
                return true;
            }

            for(int j=0;j<s.length();j++){
                if(isMatch(s.substr(j), p)){
                    return true;
                }
            }

            return false;

        }else{
            return (p[0]=='?'|| p[0]==s[0])&& !s.empty()&&isMatch(s.substr(1),p.substr(1));
        }

}

at
Labels: , , , , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts