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