Friday, March 6, 2015

44. Wildcard Matching Leetcode Java

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:
This problem is very similar to 10. Regular Expression Matching Leetcode
but in my opinion is easier than that one. Because '*' is matching any sequence and do not have to consider the preceding char.
1. Dynamic solution:
Just like problem 10, using a two dimensional array to store the match information for s(0,i) and p(0,j). But unfortunately, this problem require much less memory usage, the two dimensional array will exceed the memory limit.
2. Greedy and dynamic programming:
Since there is no preceding char issue, so any sequence without '*' in p must match sequence in s, because in this problem '*' can not skip preceding element.
Since '*' can match any sequence of characters, we can consider '*' as an empty char or a "skip char", which can skip any length of chars in s. like s="fabcd" p="f*cd" the '*' skipped "ab". Any sequence before '*' must be matched. Any '*' is a new start for matching s and p, so we can dump all the preceding sequence so eg. s="efg,seq,abc,seq,abc,seq", p="efg,*abc,*,seq" when we match to the first '*', we don't have to go back to consider the sequence before '*' now s="seq,abc,seq,abc,seq" and p="*abc,*,seq", then we iteratively check how many chars in s will be skipped because of '*' until we can match to next '*' or the end of s. in this case, "seq," will be skipped, then we can match "seq,abc," with "*abc," before the second'*', since we find this star we dump all the sequences that have been matched, now s="seq,abc,seq" p="*,seq", then we can check if they can match using same technique. 
The reason that we don't have to consider all the matched sequence before '*' is that, the essential of this problem is to match all the non '*' chars in p with chars in s. So as long as all the chars before '*', '*' can take care of skipping chars in s.
Tips:
Using two variables to track last position of '*' and how many char has been skipped in s.
Time complexity: O(m*n)   
 public boolean isMatch(String s, String p) {  
    if(s==null || p==null) return false;  
    if(p.length()==0) return s.length()==0;  
    int i=0;  
    int j=0;  
    int ii=-1;  
    int jj=-1;  
    while(i<s.length()){  
      if(j<p.length() && p.charAt(j)=='*'){  
        jj=j;  
        ii=i;  
        j++;  
      }  
      else if(j<p.length() && (s.charAt(i)==p.charAt(j) || p.charAt(j)=='?')){  
        i++;  
        j++;  
      }  
      else {  
        if(jj==-1) return false;  
        j=jj;  
        i=ii+1;  
      }  
    }  
    while(j<p.length()&&p.charAt(j)=='*') j++;  
    return j==p.length();  
   }  

No comments:

Post a Comment