Wildcard Matching 44

Description

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

Hint

DP backtracking Greedy

Method

DP method 2d dp dp[i][j] s(0 -i) match t(0 -j) init : dp[0][0] = true; for i (s 1 - n - 1) dp[i][0] = false;

   for j (t : 1 - m)
    if (t[j - 1] == '*'){
        dp[0][j] = true;
    } else {
       break;
    }

transition : if(p.charAt(j-1)!='*'){ // dp[i][j]=dp[i-1][j-1] && (p.charAt(j-1)==s.charAt(i-1) || p.charAt(j-1)=='?');

//           }
//           else{
//               dp[i][j]=dp[i-1][j]||dp[i][j-1];
//           }

method two :
four point 
 2 normal point 
 2 for star
  when i , j char is normal char just compare each other 
  i ++; j ++
  if not if j is at star
  mark it star = j;
          s-star = i;
          j++;

  if star has showing 
     forward i until finished 
  else false;

Time & Space

one : o(n^2) two : 0(n)

Code

public class Solution {
    public boolean isMatch(String s, String p) {
    //   int m=s.length(),n=p.length();
    //   boolean dp[][]=new boolean[m+1][n+1];
    //   dp[0][0]=true;
    //   for(int i=1;i<m;i++){
    //       dp[i][0]=false;
    //   }

    //   for(int i=1;i<=n;i++){
    //       if(p.charAt(i-1)=='*'){
    //          dp[0][i]=true;
    //       }
    //       else{break;}
    //   }

    //   for(int i=1;i<=m;i++){

    //       for(int j=1;j<=n;j++){
    //           if(p.charAt(j-1)!='*'){
    //               dp[i][j]=dp[i-1][j-1] && (p.charAt(j-1)==s.charAt(i-1) || p.charAt(j-1)=='?');

    //           }
    //           else{
    //               dp[i][j]=dp[i-1][j]||dp[i][j-1];
    //           }
    //       }
    //   }

    //   return dp[m][n];
    char[] cs=s.toCharArray();
    char[] ps=p.toCharArray();
    int m=cs.length,n=ps.length;
    int i=0,j=0;
    int star=-1,s_star=0;
      while(i<m){
          if(j<n && i<m &&(ps[j]=='?'||ps[j]==cs[i])){
              i++;
              j++;
          }
          else if(j<n && ps[j]=='*'){
              star=j;
              s_star=i;
              j++;
          }
          else if(star!=-1){
              j=star+1;
              s_star+=1;
              i=s_star;
          }
          else {return false;}
      }

      while(j<n && ps[j]=='*'){
          j++;
      }
      return j==n;
    }
}