[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") → 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
        }
    };
原文地址:https://www.cnblogs.com/Xylophone/p/3911877.html