首页 > 代码库 > [LeetCode] Wildcard Matching

[LeetCode] 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") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "*") → trueisMatch("aa", "a*") → trueisMatch("ab", "?*") → trueisMatch("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        }    };