Leetcode–Wildcard Matching

The Problem:

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

Notes:

  1. I used a pretty straightforward recursive solution but exceeds time limit. Here is a iterative solution, it records the index of both p and s whenever a * occurs in p, and if this round goes to a dead end, start from the recorded indices.

Java Solution

public class Solution {
    public boolean isMatch(String s, String p) {
        int slen = s.length();
        int plen = p.length();
 
        if(plen==0){
            if(slen==0)return true;
            else return false;
        }
        
        int i = 0;
        int j = 0;
        int nxts = -1;
        int nxtp = -1;
//here only use i as ending condition, for the case j reach the end with no match, 
//it can go back to recorded index and match again
while(i < slen){
            if  (j < plen && (p.charAt(j)=='?' || p.charAt(j)==s.charAt(i)))
            {
                i++;
                j++;
            } 
            else if(j < plen && p.charAt(j)=='*'){
                nxtp = j;
                nxts = i;
//only increase j
                j++;
            }
            else {
                if(nxtp==-1){
                    return false;
                }
                else{
                    nxts++;
                    i = nxts;
// only increase i by 1 from previous recorded index, 
//which means include s[i] to the match of *
//(not set i up to the failure point)
                    j = nxtp+1;
                }
            }
        }
//if p has character left, only can be true if all the left are *
        while(j < plen && p.charAt(j)=='*'){
            j++;
        }
        
        return (j==plen);
   }
}
      
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s