Wednesday, April 9, 2014

Leetcode: Wildcard Matching

'?' 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:

Using a "greedy" approach, where we try to reach the end of p, saving the last occurrence of '*' but  match an * by the empty string. In the case that we arrive to a state we cannot go on, we retrieve the saved state and we make the * to match one character more each than the previous time.

public class Solution {
    public boolean isMatch(String s, String p) {
        int si = 0, pi = 0;
        int ss=-1, pp =-1;
        while(si<s.length())
        {
            if(si<s.length() && pi<p.length() && s.charAt(si)==p.charAt(pi)){si++; pi++; continue;}
            if(si<s.length() && pi<p.length() && p.charAt(pi)=='?'){si++; pi++; continue;}
            if(si<s.length() && pi<p.length() && p.charAt(pi)=='*'){ss=si; pp=pi++; continue;}
            if(pp!=-1 && pp <p.length()){si =ss++; pi=pp +1; continue;}
            return false;
        }
        while (pi<p.length() && p.charAt(pi)=='*'){pi++;}
        return pi==p.length();
    }
}

No comments :

Post a Comment