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
|
// Inspired by https://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html
const matchHere = (pattern, text) => {
if (pattern.length === 0) return true;
// If pattern ends with $, match end of string
if (pattern[0] === '$' && pattern.length === 1) return text.length === 0;
// If next char is '*', match zero or more occurrences of prev char
if (pattern[1] === '*') return matchStar(pattern[0], pattern.slice(2), text);
// Match . or literal character
if (text.length !== 0 && (pattern[0] === '.' || pattern[0] === text[0])) {
return matchHere(pattern.slice(1), text.slice(1));
}
return false;
};
const matchStar = (prevChar, pattern, text) => {
// Try matching zero occurrences first
if (matchHere(pattern, text)) return true;
// Then, match one or more occurrences of prevChar
while (text.length > 0 && (text[0] === prevChar || prevChar === '.')) {
text = text.slice(1);
if (matchHere(pattern, text)) return true;
}
return false;
};
const match = (pattern, text) => {
// Handle ^ anchor at the beginning
if (pattern[0] === '^') {
return matchHere(pattern.slice(1), text);
}
// Otherwise, check the entire string
for (let i = 0; i <= text.length; i++) {
if (matchHere(pattern, text.slice(i))) return true;
}
return false;
};
const assertEqual = (actual, expected, testName) =>
console.log(actual === expected ? `Passed: ${testName}` : `Failed: ${testName}. Expected ${expected} but got ${actual}`);
assertEqual(match("ab*c", "ac"), true, "Star match 'ab*c' vs 'ac' (zero occurrences)");
assertEqual(match("ab*c", "abbbc"), true, "Star match 'ab*c' vs 'abbbc' (multiple occurrences)");
assertEqual(match("^ab.*c$", "abc"), true, "Complex match '^ab.*c$' vs 'abc'");
assertEqual(match("^ab.*c$", "abcd"), false, "Complex mismatch '^ab.*c$' vs 'abcd'");
|