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.
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5public class PatternMatcher {
6 public bool MatchesPattern(string word, string pattern) {
7 var mapPtoW = new Dictionary<char, char>();
8 var mapWtoP = new Dictionary<char, char>();
9
10 for (int i = 0; i < pattern.Length; i++) {
11 char w = word[i];
12 char p = pattern[i];
13
14 if (!mapPtoW.ContainsKey(p) && !mapWtoP.ContainsKey(w)) {
15 mapPtoW[p] = w;
16 mapWtoP[w] = p;
17 } else if (mapPtoW[p] != w || mapWtoP[w] != p) {
18 return false;
19 }
20 }
21 return true;
22 }
23
24 public List<string> FindAndReplacePattern(string[] words, string pattern) {
25 return words.Where(word => MatchesPattern(word, pattern)).ToList();
26 }
27}
28C# uses Dictionary to map pattern to word characters. The function logic is comparable to other implementations, employing LINQ for filtering 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.