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.
1#include <stdio.h>
2#include <stdbool.h>
3#include <string.h>
4
5bool matchesPattern(char* word, char* pattern) {
6 char mapPtoW[128] = {0};
7 char mapWtoP[128] = {0};
8
9 for (int i = 0; i < strlen(pattern); i++) {
10 char w = word[i];
11 char p = pattern[i];
12
13 if (!mapPtoW[p] && !mapWtoP[w]) {
14 mapPtoW[p] = w;
15 mapWtoP[w] = p;
16 }
17 else if (mapPtoW[p] != w || mapWtoP[w] != p) {
18 return false;
19 }
20 }
21 return true;
22}
23
24char** findAndReplacePattern(char** words, int wordsSize, char* pattern, int* returnSize) {
25 char** result = malloc(wordsSize * sizeof(char*));
26 int resIndex = 0;
27
28 for (int i = 0; i < wordsSize; i++) {
29 if (matchesPattern(words[i], pattern)) {
30 result[resIndex++] = words[i];
31 }
32 }
33 *returnSize = resIndex;
34 return result;
35}
36This C code defines a function matchesPattern to check if a particular word matches the pattern based on bijective mappings. The primary function findAndReplacePattern iterates over each word, using matchesPattern to verify matches, and stores the 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.
1import
The Java solution calculates a pattern encoding for words and pattern using the index of character first appearances. It uses these encodings to match words to the pattern.