Wildcard Matching

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

------------------ thinking ------------------------------------------
1. BUG!!!! please remember to add additional element checking for "" (empty) of s and p
2. when the length of p minus the number of '*' is bigger than s, there is no way we need to continue, return false directly
https://oj.leetcode.com/discuss/22743/python-dp-solution
--------------------- codes ------------------------------------------
class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        // get len(s) and make sure len(s) >= len(p) - count(p, '*')
        int slen = 0;
        int plen = 0;
        for (auto q1 = s; *q1 != '\0'; q1++) {
            slen++;
        }
        int star_cnt = 0;
        for (auto q1 = p; *q1 != '\0'; q1++) {
            if (*q1 == '*') star_cnt++;
            plen++;
        }
        // additional time saving step here
        if (star_cnt + slen < plen) {
            return false;
        }
        //for (auto q1 = s, q2 = p; *q1 != '\0' || *q2 != '\0'; q1++) {
        //    while (*q2 == '*') q2++;
        //    if (*q1 == '\0') {
        //        if (*q2 != '\0') return false;
        //        break;
        //    }
        //    if (*q2 != '\0') q2++;
        //    size++;
        //}
        bool T[slen + 1][plen+1];
        T[0][0] = true;
        //bug here
        for (int j = 1; j < plen+1; j++) {
            T[0][j] = T[0][j-1] && (p[j-1] == '*');
        }
        for (int i = 1; i < slen+1; i++) {
            T[i][0] = (p[0] == '*');
            for (int j = 1; j < plen+1; j++) {
                T[i][j] = false;
                if (p[j-1] == '*') {
                    if (T[i-1][j] || T[i][j-1]) {
                        T[i][j] = true;
                    }
                } else if (p[j-1] == '?' || p[j-1] == s[i-1]) {
                    if (T[i-1][j-1]) {
                        T[i][j] = true;
                    }
                }
            }
        }
        return T[slen][plen];
    }
};