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.
1def matchesPattern(word, pattern):
2 mapPtoW, mapWtoP = {}, {}
3 for w, p in zip(word, pattern):
4 if p not in mapPtoW and w not in mapWtoP:
5 mapPtoW[p] = w
6 mapWtoP[w] = p
7 elif mapPtoW.get(p) != w or mapWtoP.get(w) != p:
8 return False
9 return True
10
11
12def findAndReplacePattern(words, pattern):
13 return [word for word in words if matchesPattern(word, pattern)]
14This Python code leverages dictionaries to store character mappings from pattern to word and vice versa. The function matchesPattern is a helper used within findAndReplacePattern to filter out non-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#include <string>
#include <unordered_map>
using namespace std;
string encodePattern(const string& str) {
unordered_map<char, int> map;
string result;
int index = 0;
for (char c : str) {
if (map.find(c) == map.end()) {
map[c] = ++index;
}
result += to_string(map[c]);
}
return result;
}
vector<string> findAndReplacePattern(const vector<string>& words, const string& pattern) {
vector<string> result;
string encodedPattern = encodePattern(pattern);
for (const string& word : words) {
if (encodePattern(word) == encodedPattern) {
result.push_back(word);
}
}
return result;
}
This C++ code derives encoding for both pattern and words using the first occurrence index, facilitating a simple comparison to filter matching words.