Leetcode 10 - Regular expression matching

Note:

  • DFS witn memo
    • DP is too hard so I guess I’ll use DFS instead.
    • Base case: when either i or j is bigger than their length, it means we’ve searched all chars in both strs, return true.
    • Because of the specialty of *, we have an if-else statement based on whether the next char is * or not.
      • If it is, there are two situations: Use it at least once or ignore its preceding char.
        • Note: if we are gonna use it, the premise is that (s[i] === p[j] || p[j] === '.').
      • If it is not, we just need to check if (s[i] === p[j] || p[j] === '.').
    • Some tricky parts:

Question:

Given an input string s and a pattern p, implement regular expression matching with support for ‘.’ and ‘*’ where:

  • ‘.’ Matches any single character.​​​​
  • ‘*’ Matches zero or more of the preceding element.
  • The matching should cover the entire input string (not partial).

Example:

1
2
3
Input: s = "aab", p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

Code:

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
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function (s, p) {
const sLen = s.length;
const pLen = p.length;
let map = {};
return dfs(0, 0);

function dfs(i, j) {
if (map[i + ':' + j] != undefined) return map[(i, j)];
if (j >= pLen && i >= sLen) return true;

const match = (i < sLen) && (s[i] === p[j] || p[j] === '.');
let tmp = false;

if (j + 1 < pLen && p[j + 1] === '*') {
tmp = (match && dfs(i + 1, j)) || dfs(i, j + 2);
} else {
tmp = match && dfs(i + 1, j + 1);
}
map[i + ':' + j] = tmp;
return tmp;
}
};