Leetcode 44 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: use DP, pay attention when char is *, dp[i][j-1] is matching 0, dp[i-1][j] is matching 1+.

 public class Solution {  
   public boolean isMatch(String s, String p) {  
     int m=s.length();  
     int n=p.length();  
     boolean[][] dp=new boolean[m+1][n+1];  
     for (int i=0; i<=m; i++) {  
       for (int j=0; j<=n; j++) {  
         if (i==0) {  
           if (j==0) dp[i][j]=true;  
           else if (p.charAt(j-1)=='*') dp[i][j]=dp[i][j-1];  
           else dp[i][j]=false;  
         }  
         else if (j==0) dp[i][j]=false;  
         else if (p.charAt(j-1)=='?') dp[i][j]=dp[i-1][j-1];  
         else if (p.charAt(j-1)=='*') dp[i][j]=dp[i-1][j] || dp[i][j-1];  
         else if (s.charAt(i-1)==p.charAt(j-1)) dp[i][j]=dp[i-1][j-1];  
         else dp[i][j]=false;  
       }  
     }  
     return dp[m][n];  
   }  
 }  

Solution 2: Optimize the space to O(n):

 public class Solution {  
   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];  
   }  
 }  

Solution 3: An O(n) solution:

 public class Solution {  
   public boolean isMatch(String s, String p) {  
     int m=s.length(), n=p.length();  
     int i=0, j=0;  
     int match=-1, star=-1;  
     while (i<m) {  
       if (j<n && (p.charAt(j)=='?' || s.charAt(i)==p.charAt(j))) {  
         i++;  
         j++;  
       }  
       else if (j<n && p.charAt(j)=='*') {  
         match=i;  
         star=j++;  
       }  
       else if (star!=-1) {  
         j=star+1;  
         i=++match;  
       }  
       else return false;  
     }  
     while (j<n && p.charAt(j)=='*') j++;  
     return j==n;  
   }  
 }