Regular Expression Match

• Time : O(nm)
• Space : O(1)

c++

int Solution::isMatch(const string A, const string B) {
    int n = A.length(), m = B.length();
    int i = 0, j = 0, si = -1, sj = -1;
    while(i < n) {
        if(A[i] == B[j] or B[j] == '?') {
            i++;
            j++;
        } else if(B[j] == '*') {
            si = i;
            sj = j;
            j++;
        } else if(sj != -1) {
            i = si + 1;
            j = sj + 1;
            si++;
        } else return 0;
    }

    while(j < m and B[j] == '*') j++;
    return j == m;
}