# leetcode 44. Wildcard Matching

## recursive
Use `if(recnum > currec + 1) return false;` to avoid unnecessary recursive. It return false if this star partition isn't the last star partition has be detected. It works because the remaining string s will only get shorter, and if the remaining part of string p can't match the remaining string s now, then it is even less likely to match a shorter string s.

class Solution {
public:
    int recnum = 0;
    bool check(string &s, string &p, int i, int j){
        int s_size = s.size(), p_size = p.size(), currec = recnum;
        if(i == s_size && j == p_size) return true;
        if(i == s_size && p[j] == '*') return check(s, p, i, j + 1);
        if(i == s_size || j == p_size) return false;
        if(s[i] == p[j] || p[j] == '?') return check(s, p, i + 1, j + 1);
        if(p[j] == '*'){
            while(p[j] == '*'){
                j++;
                if(j == p_size) return true;
            }
            recnum++;
            for(; i < s_size; i++){
                if(p[j] != '?' && s[i] != p[j]) continue;
                if(check(s, p, i, j)) return true;
                if(recnum > currec + 1) return false;
            }
        }
        return false;
    }
        
    bool isMatch(string s, string p) {
        return check(s, p, 0, 0);
    }
};

## iterator
Modified from recursive, as same, no need to consider about the star partition before the last one which be detected.

class Solution {
public: 
    bool isMatch(string s, string p) {
        int s_size = s.size(), p_size = p.size(), i = 0, j = 0, istar = -1, jstar = -1;
        while(i < s_size || j < p_size){
            if(i == s_size && p[j] == '*'){
                j++;
                continue;
            }
            if(i == s_size || j == p_size){
                if(jstar != -1){
                    i = istar;
                    j = jstar;
                    jstar = -1;
                    continue;
                }
                return false;
            } 
            
            if(s[i] == p[j] || p[j] == '?'){
                i++;
                j++;
                continue;
            }
            if(p[j] == '*'){
                while(p[j] == '*'){
                    j++;
                    if(j == p_size) return true;
                }
                jstar = j - 1;
                for(; i < s_size; i++)
                    if(s[i] == p[j] || p[j] == '?') break;
                if(i == s_size) return false;
                istar = i + 1;
                continue;
            }
            if(jstar != -1){
                i = istar;
                j = jstar;
                jstar = -1;
                continue;
            }
            return false; 
        }
        return true;
    }
};

###### tags: `leetcode` `c++`