Sponsored
Sponsored
In this approach, we establish a one-to-one mapping for each letter in the pattern to letters in each word. To do this, we use two maps or dictionaries: one for mapping pattern to word letters and another for mapping word to pattern letters. Both maps are used to ensure that the mapping is bijective (i.e., one-to-one).
Time Complexity: O(n * m), where n is the number of words and m is the word length.
Space Complexity: O(m), for the maps storing character mappings.
1function matchesPattern(word, pattern) {
2 const mapPtoW = new Map();
3 const mapWtoP = new Map();
4
5 for (let i = 0; i < pattern.length; i++) {
6 const w = word[i];
7 const p = pattern[i];
8
9 if (!mapPtoW.has(p) && !mapWtoP.has(w)) {
10 mapPtoW.set(p, w);
11 mapWtoP.set(w, p);
12 } else if (mapPtoW.get(p) !== w || mapWtoP.get(w) !== p) {
13 return false;
14 }
15 }
16 return true;
17}
18
19function findAndReplacePattern(words, pattern) {
20 return words.filter(word => matchesPattern(word, pattern));
21}
22This JavaScript code utilizes the Map object to create bidirectional character mappings for pattern and word comparison, employing filter to derive matching words.
In this approach, we map each character of the string to its first occurrence index in the string. This creates a unique encoding pattern for comparison. Two strings match if they have the same encoding pattern.
Time Complexity: O(n * m), where n is the number of words and m is the word length.
Space Complexity: O(m), for storing encoded strings and maps.
1
The JavaScript code compares encoded strings of the pattern and words, where encoding relies on initial character indices to establish a unique format for verification.