-
Notifications
You must be signed in to change notification settings - Fork 0
/
Regular_Expression_Matching.js
60 lines (45 loc) · 1.83 KB
/
Regular_Expression_Matching.js
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// -------------------------- Description ------------------------------------------
// 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:
// Input: s = "aa", p = "a"
// Output: false
// Explanation: "a" does not match the entire string "aa".
// Example 2:
// Input: s = "aa", p = "a*"
// Output: true
// Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
// Example 3:
// Input: s = "ab", p = ".*"
// Output: true
// Explanation: ".*" means "zero or more (*) of any character (.)".
// Constraints:
// 1 <= s.length <= 20
// 1 <= p.length <= 20
// s contains only lowercase English letters.
// p contains only lowercase English letters, '.', and '*'.
// It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.
// ---------------------------------------------------------------------------------
var isMatch = function (s, p) {
const memo = new Map();
const dp = (i, j) => {
if (memo.has(`${i}-${j}`)) return memo.get(`${i}-${j}`);
if (j === p.length) return i === s.length;
const firstMatch = i < s.length && (p[j] === "." || p[j] === s[i]);
let ans;
if (j + 1 < p.length && p[j + 1] === "*") {
ans = dp(i, j + 2) || (firstMatch && dp(i + 1, j));
} else {
ans = firstMatch && dp(i + 1, j + 1);
}
memo.set(`${i}-${j}`, ans);
return ans;
};
return dp(0, 0);
};
// Example usage:
console.log(isMatch("aa", "a")); // Output: false
console.log(isMatch("aa", "a*")); // Output: true
console.log(isMatch("ab", ".*")); // Output: true