1
class Solution {
2
  public boolean isMatch(String s, String p) {
3
    int i = 0;
4
    int j = 0;
5
    int starIdx = -1;
6
    int lastMatch = -1;
7

8
    while (i < s.length()) {
9
      if (j < p.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')) {
10
        i++;
11
        j++;
12
      } else if (j < p.length() && p.charAt(j) == '*') {
13
        starIdx = j;
14
        lastMatch = i;
15
        j++;
16
      } else if (starIdx != -1) {
17
        // there is a no match and there was a previous star, we will reset the j to indx after
18
        // star_index
19
        // lastMatch will tell from which index we start comparing the string if we encounter * in
20
        // pattern
21
        j = starIdx + 1;
22
        lastMatch++; // we are saying we included more characters in * so we incremented the index
23
        i = lastMatch;
24

25
      } else {
26
        return false;
27
      }
28
    }
29

30
    while (j < p.length() && p.charAt(j) == '*') j++;
31

32
    if (i != s.length() || j != p.length()) return false;
33

34
    return true;
35
  }
36
}