leetCode/string/regularExpressionMatching/regularExpressionMatching.js at master · codalife/leetCode · 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
38
39
40
41
/**
 * '.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */

// RECURSIVE !!!!
function isMatch(s, p) {
  if (p.length === 0) {
    return s.length === 0;
  }
  if (s === p) {
    return true;
  }

  const firstMatch = s.length > 0 && (s[0] === p[0] || p[0] === '.');

  if (p.length > 1 && p[1] === '*') {
    return (
      isMatch(s, p.substring(2)) || (firstMatch && isMatch(s.substring(1), p))
    );
  } else {
    return firstMatch && isMatch(s.substring(1), p.substring(1));
  }
}