44. Wildcard Matching

[huimeich]

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

[huimeich]

class Solution {
public:
    bool isMatch(string s, string p) {
        if (s.empty() && p.empty()) return true;
        int pbegin = p.find('*');
        int pend = p.size()-1;
        int send = s.size()-1;
        if (pbegin == std::string::npos) {
            if (pend != send) return false;
            pbegin = pend+1;
        }
        if (pbegin > s.size()) return false;

        for (int i = 0; i < pbegin; i++) {
            if (s[i] != p[i] && p[i] != '?') return false;
        }
        for (; send >= pbegin; send--,pend--) {
            if (p[pend] == '*') break;
            if (s[send] != p[pend] && p[pend] != '?') return false;
        }
        return isMatch(s,p,pbegin,pbegin,send,pend);
    }
    bool isMatch(string s, string p, int sbegin, int pbegin, int send, int pend) {
        while (pbegin <= pend && p[pbegin] == '*') pbegin++;
        if (pbegin > pend) return true;
        if (sbegin > send) return false;
        int len = 0;
        while (pbegin <= pend && p[pbegin+len] != '*') len++;
        int snext = findMatch(s, p.substr(pbegin,len), sbegin, send);
        if (snext == s.size()+2) return false;
        return isMatch(s, p, snext, pbegin+len, send, pend);
    }
    int findMatch(string s, string psub, int& sbegin, int send) {
        cout << psub << "\n";
        if (psub.empty()) return sbegin;
        if (sbegin > send) return sbegin;
        int j = 0;
        int i = sbegin;
        for (; i <= send;) {
            if (s[i] == psub[j] || psub[j] == '?') {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
            if (j == psub.size()) {
                return i;
            }
        }
        return (s.size()+2);
    }
};