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 <vector>
2#include <string>
3#include <unordered_map>
4using namespace std;
5
6bool matchesPattern(const string& word, const string& pattern) {
7 unordered_map<char, char> mapPtoW;
8 unordered_map<char, char> mapWtoP;
9
10 for (int i = 0; i < pattern.size(); ++i) {
11 char w = word[i];
12 char p = pattern[i];
13
14 if (mapPtoW.find(p) == mapPtoW.end() && mapWtoP.find(w) == mapWtoP.end()) {
15 mapPtoW[p] = w;
16 mapWtoP[w] = p;
17 }
18 else if (mapPtoW[p] != w || mapWtoP[w] != p) {
19 return false;
20 }
21 }
22 return true;
23}
24
25vector<string> findAndReplacePattern(const vector<string>& words, const string& pattern) {
26 vector<string> result;
27 for (const string& word : words) {
28 if (matchesPattern(word, pattern)) {
29 result.push_back(word);
30 }
31 }
32 return result;
33}
34This C++ solution uses the same bijective mapping approach as the C solution but leverages STL containers like unordered_map for mappings and vector to store results.
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
In this Python implementation, the encodePattern function maps each character to its first occurrence index, creating a consistent way to compare pattern and words.