44. Wildcard Matching

a kind of DFS in java

boolean comparison(String str, String pattern) {
        int s = 0, p = 0, match = 0, starIdx = -1;            
        while (s < str.length()){
            // advancing both pointers
            if (p < pattern.length()  && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){
                s++;
                p++;
            }
            // * found, only advancing pattern pointer
            else if (p < pattern.length() && pattern.charAt(p) == '*'){
                starIdx = p;
                match = s;
                p++;
            }
           // last pattern pointer was *, advancing string pointer
            else if (starIdx != -1){
                p = starIdx + 1;
                match++;
                s = match;
            }
           //current pattern pointer is not star, last patter pointer was not *
          //characters do not match
            else return false;
        }

        //check for remaining characters in pattern
        while (p < pattern.length() && pattern.charAt(p) == '*')
            p++;

        return p == pattern.length();
}

DP O(mn)

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> memo(m + 1, vector<bool>(n + 1, false));
        memo[0][0] = true;
        for (int j = 1; j <= n && p[j - 1] == '*'; j++)
            for (int i = 0; i <= m; i++)
                memo[i][j] = true;

        //int flag = 0;
        for (int j = 1; j <= n; j++) {
            //flag = memo[0][j - 1];
            for (int i = 1; i <= m; i++) {
                if (p[j - 1] != '*')
                    memo[i][j] = memo[i - 1][j - 1] && (p[j - 1] == '?' || s[i - 1] == p[j - 1]);
                else {
                    memo[i][j] = memo[i][j - 1] || memo[i - 1][j];
                }
                //flag |= (memo[i][j]);
            }
            //flag >>= 1;
        }

        //  for (int i = 0; i <= m; i++) {cout<<endl;
        //     for (int j = 0; j <= n; j++) cout<<memo[i][j];}


        return memo[m][n];
    }
};

DP O(mn) with something wrong(お前バカだわ。）

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> memo(m + 1, vector<bool>(n + 1, false));
        memo[0][0] = true;
        for (int j = 1; j <= n && p[j - 1] == '*'; j++)
            for (int i = 0; i <= m; i++)
                memo[i][j] = true;

        int flag = 0;
        for (int j = 1; j <= n; j++) {
            flag = memo[0][j - 1];
            for (int i = 1; i <= m; i++) {
                if (p[j - 1] != '*')
                    memo[i][j] = memo[i - 1][j - 1] && (p[j - 1] == '?' || s[i - 1] == p[j - 1]);
                else {
                    memo[i][j] = memo[i][j] || (flag & 1);
                }
                flag |= (memo[i][j]);
            }
            //flag >>= 1;
        }

         for (int i = 0; i <= m; i++) {cout<<endl;
            for (int j = 0; j <= n; j++) cout<<memo[i][j];}


        return memo[m][n];
    }
};