[LeetCode44]Wildcard Matching

本文主要是介绍[LeetCode44]Wildcard Matching，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

Analysis:

Greedy method

For each element in s
If *s==*p or *p == ? which means this is a match, then goes to next element s++ p++.
If p=='*', this is also a match, but one or many chars may be available, so let us save this *'s position and the matched s position.
If not match, then we check if there is a * previously showed up,
if there is no *, return false;
if there is an *, we set current p to the next element of *, and set current s to the next saved s position.

e.g.

abed
?b*d**

a=?, go on, b=b, go on,
e=*, save * position star=3, save s position ss = 3, p++
e!=d, check if there was a *, yes, ss++, s=ss; p=star+1
d=d, go on, meet the end.
check the rest element in p, if all are *, true, else false;

Note that in char array, the last is NOT NULL, to check the end, use "*p" or "*p=='\0'".

Java

public boolean isMatch(String s, String p) {int slen = s.length();int plen = p.length();int i = 0, j=0;int star = -1;int sp = 0;while(i<slen){while(j<plen && p.charAt(j)=='*'){star = j++;sp = i;}if(j==plen || (s.charAt(i)!=p.charAt(j)&&p.charAt(j)!='?')){if(star<0) return false;else {j = star+1;i = sp++;}}else {i++;j++;}}while(j<plen && p.charAt(j)=='*'){j++;}return j == plen;}

c++

bool isMatch(const char *s, const char *p) {const char* star = NULL;const char* ss = s;while(*s){if((*p=='?') || *p==*s){s++;p++;continue;}if(*p=='*'){star = p++;ss = s;continue;}if(star){p = star+1;s=++ss;continue;}return false;}while(*p=='*'){p++;}return !*p;}

这篇关于[LeetCode44]Wildcard Matching的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---