leetcode-javascript/solutions/0044-wildcard-matching.js at development · Anuj9826/leetcode-javascript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
    * Wildcard Matching
    * Time Complexity: O(S * P)
    * Space Complexity: O(1)
*/
var isMatch = function (s, p) {
  let stringWalker = 0;
  let patternWalker = 0;
  let lastStarPatternPosition = -1;
  let currentMatchPoint = -1;

  while (stringWalker < s.length) {
    if (patternWalker < p.length && (p[patternWalker] === '?' || p[patternWalker] === s[stringWalker])) {
      stringWalker++;
      patternWalker++;
    } else if (patternWalker < p.length && p[patternWalker] === '*') {
      lastStarPatternPosition = patternWalker;
      currentMatchPoint = stringWalker;
      patternWalker++;
    } else if (lastStarPatternPosition !== -1) {
      patternWalker = lastStarPatternPosition + 1;
      currentMatchPoint++;
      stringWalker = currentMatchPoint;
    } else {
      return false;
    }
  }

  while (patternWalker < p.length) {
    if (p[patternWalker] !== '*') {
      return false;
    }
    patternWalker++;
  }

  return true;
};