44 Wildcard Matching *****imp & hard

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for'?'and'*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

• [x] //why use star and match to save the position when pp encounters *

when pp meets *, we mark the curt position of pp and sp, star = pp, match = sp, increment pp;

Then check to see if s.charAt(sp) == t.charAt(pp)

if not match++, sp = match, means we use the star to match the current character,

and we keep pp = star + 1 means we did not go any further, we are still in the control scope of the *

/***

s = "aa"

p = "*"

"acdcb"

"a*c?b"

***/

//star = -1;

// if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?' -> i++, j++

// else if (p.charAt(j) == '*' -> star = pp, match = sp; pp++;

//else if (star != -1 ) => match++; sp = match; pp = star + 1

// else return false

• [x] remember to check whether pp reaches the end of the p string.

class Solution {

    time: O(n)
    space: O(1)
        // if s.charAt(i) == t.charAt(j) || t.charAt(j) == '?' -> i++; j++
        // else if (t.charAt(j) == '*') => mark the pos of the curt pointers star == pp, match = sp, pp++
        // else if met the * and skip some characters in s
        // return false;

    public boolean isMatch(String s, String p) {
        if (s == null && p == null) {
            return true;
        }
        if (s == null || p == null) {
            return false;
        }
        int sp = 0;
        int pp = 0;
        int slen = s.length();
        int plen = p.length();
        int star = -1;
        int match = 0;
        while (sp < slen) {
            if (pp < plen && (s.charAt(sp) == p.charAt(pp) || p.charAt(pp) == '?')) {
                sp++;
                pp++;
            } else if (pp < plen && p.charAt(pp) == '*') {
                star = pp;
                match = sp;
                pp++;
            } else if (star != -1) {
                pp = star + 1;
                match++;
                sp = match;
            } else {
                return false;
            }
        }
         while (pp < p.length() && p.charAt(pp) == '*') {
            pp++;
        }
        return pp == p.length();
    }
}