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.
1using System.Collections.Generic;
using System.Linq;
public class PatternMatcher {
private string EncodePattern(string str) {
var map = new Dictionary<char, int>();
var encoded = new List<int>();
int index = 0;
foreach (char c in str) {
if (!map.ContainsKey(c)) {
map[c] = index++;
}
encoded.Add(map[c]);
}
return string.Join("", encoded);
}
public List<string> FindAndReplacePattern(string[] words, string pattern) {
string encodedPattern = EncodePattern(pattern);
return words.Where(word => EncodePattern(word) == encodedPattern).ToList();
}
}
Utilizing string encoding based on initial occurrences, this C# code identifies matching words by comparing encoded patterns of words and the pattern itself.