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.
1import java.util.*;
2
3public class PatternMatch {
4 public boolean matchesPattern(String word, String pattern) {
5 Map<Character, Character> mapPtoW = new HashMap<>();
6 Map<Character, Character> mapWtoP = new HashMap<>();
7
8 for (int i = 0; i < pattern.length(); i++) {
9 char w = word.charAt(i);
10 char p = pattern.charAt(i);
11
12 if (!mapPtoW.containsKey(p) && !mapWtoP.containsKey(w)) {
13 mapPtoW.put(p, w);
14 mapWtoP.put(w, p);
15 } else if (!Objects.equals(mapPtoW.get(p), w) || !Objects.equals(mapWtoP.get(w), p)) {
16 return false;
17 }
18 }
19 return true;
20 }
21
22 public List<String> findAndReplacePattern(String[] words, String pattern) {
23 List<String> result = new ArrayList<>();
24 for (String word : words) {
25 if (matchesPattern(word, pattern)) {
26 result.add(word);
27 }
28 }
29 return result;
30 }
31}
32The Java solution utilizes HashMap to create mappings and check if a word matches the given pattern. The logic is consistent with other languages, using a helper function matchesPattern.
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
This C program calculates an encoded representation for the pattern and each word using indices of first occurrences. It then compares these encodings to determine if a word matches the pattern.