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
From Other:
class Solution { public: bool isMatch(const char *s, const char *p) { if (!*p && !*s) return true; // both empty, so sad but true if (*p == *s) return isMatch(s + 1, p + 1); // match! else if (*p == ‘?‘ && *s) return isMatch(s + 1, p + 1); // weird match! else if (*p == ‘*‘) { int ret = false; while (*p == ‘*‘) ++p; // I only need just one starlet ;) if (!*p) return true; // ends with star, the Universe can fit into it now! while (*s) { // brute force match const char *ts = s, *tp = p; while ((*ts == *tp || *tp == ‘?‘) && *ts) { if (*tp == ‘*‘) break; ++ts; ++tp; } if (!*ts && !*tp) return true; // both empty // *tp is * then ok, otherwise no exact match :( if (*tp == ‘*‘) { // we don‘t need to concern ourself with more exact matches as the * would take care of it, // and for rest brute force matching will be done ret |= isMatch(ts, tp); return ret; } if (!*ts) return false; // search exhausted yo! p has more than s can handle :O ++s; } return ret; } else return false; // WAT } };
[LeetCode] Wildcard Matching,布布扣,bubuko.com
原文：http://www.cnblogs.com/Xylophone/p/3911877.html