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


  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(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)))
            else if(j < plen && p.charAt(j)=='*'){
                nxtp = j;
                nxts = i;
//only increase j
            else {
                    return false;
                    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)=='*'){
        return (j==plen);

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s