890. Find and Replace Pattern
Problem Description
The task is to find all words from a given list that match a specific pattern. A word matches the pattern if we can map each letter in the pattern to a different letter (forming a bijection) such that when we replace the letters in the pattern based on this mapping, we get the word from the list.
For example, if the pattern is "abb" and one of the words is "cdd", there is a match because we can map 'a' to 'c' and 'b' to 'd'. However, if another word in the list is "cde", it does not match the "abb" pattern because 'a' maps to 'c', but 'b' would have to map to both 'd' and 'e' for the word to match, which is not allowed since a bijection requires each letter to map to a unique letter.
The problem necessitates that no two different letters in the pattern can map to the same letter in the words, maintaining the uniqueness of the bijection.
Intuition
The solution approach involves checking for each word if there's a bijection with the pattern. This is done by creating two mappings: one for the word and one for the pattern. As we iterate through the characters of a word and the pattern simultaneously, we can establish a correspondence between the two.
The intuition is that if a word follows the pattern, each occurrence of a particular character in the pattern should be mapped to the same character in the word, and vice versa. For instance, pattern "abb" and word "xyz" do not match because 'a' is mapped to 'x', but 'b' has to be mapped to both 'y' and 'z', which violates the rules.
By utilizing two arrays indexed by the ASCII values of the characters, we can store the order in which each character appears. If at any point we find that the current mapping does not match (i.e., the current character of the word was previously mapped with a different character of the pattern or vice versa), we can conclude that the word does not match the pattern.
Therefore, we compare the mapping of the characters at each index. If they do not match, it means this particular word does not follow the pattern. If we reach the end without discrepancies, the word matches the pattern.
This comparison continues for each word in the list, and all matching words are collected and returned.
Solution Approach
In the provided solution, the objective was to compare a given word with a pattern. The essence of the solution lies in the algorithm that maps each character in the pattern to a character in the word and checks for consistency throughout the string.
Here is a step-by-step process of how the Solution
class implements this algorithm:
-
A helper function
match
is defined, which takes two stringss
(the word from the list) andt
(the pattern) and determines whethers
matchest
. -
Two arrays of integers,
m1
andm2
, are initialized with a length of 128. This size is chosen to cover all standard ASCII values, ensuring that each character from the word and the pattern can be mapped to an index in these arrays. Initially, all elements ofm1
andm2
are set to0
. -
The function then iterates through the characters of both the pattern and the word simultaneously using a
zip
function in Python. -
For every pair of characters
(a, b)
froms
andt
, their ASCII values are used as indices inm1
andm2
. -
On each iteration, indexed by
i
(starting at 1 to avoid the 0 initial values ofm1
andm2
), it checks ifm1[ord(a)]
is not equal tom2[ord(b)]
. If they are not equal, it means that the current character mapping is not consistent with previous mappings, and hence the function returnsFalse
. -
If the condition is satisfied (i.e., the characters match the mapping), both mappings are updated with the current index
i
. This step marks the position of the latest mapping and serves to maintain consistency. If the same characters ins
andt
occur later, they must result in the same mapping index, or otherwise, they do not follow the pattern and the function would returnFalse
. -
After completing the loop, if no inconsistencies are found, the function returns
True
, signifying that the words
matches the patternt
. -
The main function in the
Solution
class uses a list comprehension that goes through all the words in the given list, applying thematch
function to each word along with the pattern. -
Only those words for which the
match
function returnsTrue
are included in the final list that the main function returns. This final list represents all the words from the input that match the given pattern.
The solution makes use of array mapping and iteration, which are fundamental in allowing the comparison of strings with patterns. This method of creating a bijection through array indexing is efficient and straightforward, as it avoids complex data structures and makes use of simple arrays, leveraging their direct access property.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Consider the pattern "abb" and the list of words ["xyz", "zzy", "yzz", "azb"]
. Let's walk through the solution approach with these examples and see which words match the pattern.
-
Take the first word "xyz" and create two arrays,
m1
andm2
, initialized to0
. -
Start iterating through "xyz" and "abb" simultaneously. Map the ASCII values of 'x' to 'a', 'y' to 'b', and 'z' to 'b' using the arrays
m1
andm2
. -
When the first characters 'x' and 'a' are encountered,
m1[ord('x')]
andm2[ord('a')]
are set to1
. -
Next, compare 'y' of "xyz" to 'b' of "abb". Since 'b' corresponds to 'y' and it's the first encounter, set
m1[ord('y')]
andm2[ord('b')]
to2
. -
Lastly, 'z' is compared to 'b'. Since 'b' is already mapped to 'y',
m1[ord('z')]
is not equal tom2[ord('b')]
, which is2
. So, the mapping is inconsistent, and "xyz" does not match "abb".
Repeat the process for the remaining words:
-
"zzy":
- 'z' maps to 'a'.
- 'z' still maps to 'b' from the previous mapping.
- 'y' maps to 'b', but 'b' is already mapped to 'z', so again, inconsistency found. "zzy" doesn't match "abb".
-
"yzz":
- 'y' maps to 'a'.
- First 'z' maps to 'b'.
- Second 'z' also maps to 'b' (consistent with previous mapping).
- Consistency is maintained, so "yzz" matches "abb".
-
"azb":
- 'a' maps to 'a'.
- 'z' maps to 'b'.
- 'b' maps to 'b', but since there's a prior mapping of 'z' to 'b', this creates inconsistency.
- "azb" does not match "abb".
In conclusion, among the words provided, only "yzz" matches the pattern "abb" using the bijection approach described in the solution.
Solution Implementation
1from typing import List
2
3class Solution:
4 def find_and_replace_pattern(self, words: List[str], pattern: str) -> List[str]:
5 # Inner function to determine if the given string s matches the pattern t
6 def is_match(s, t):
7 # Initialize two maps for characters in s and t
8 # Each map stores the index of the character from s/t encountered in the string
9 map_s, map_t = [0] * 128, [0] * 128
10 # Enumerate through the pair(s) from s and t
11 for index, (char_s, char_t) in enumerate(zip(s, t), 1):
12 # If the mappings are not equal, then s does not match the pattern t
13 if map_s[ord(char_s)] != map_t[ord(char_t)]:
14 return False
15 # Update the mapping for the current character in both s and t to the current index
16 map_s[ord(char_s)] = map_t[ord(char_t)] = index
17 # If the loops completes without returning False, s matches the pattern t
18 return True
19
20 # List comprehension to find and collect words that match the pattern
21 # It invokes the is_match function on each word with the given pattern
22 return [word for word in words if is_match(word, pattern)]
23
24# Example of usage:
25# sol = Solution()
26# matching_words = sol.find_and_replace_pattern(["abc","deq","mee","aqq","dkd","ccc"], "abb")
27# print(matching_words) # Output would be ["mee","aqq"]
28
1class Solution {
2
3 /**
4 * Filters the array of words, selecting only those that match the given pattern.
5 *
6 * @param words an array of words to be filtered based on the pattern
7 * @param pattern the pattern to which words are to be matched
8 * @return a list of words that match the pattern
9 */
10 public List<String> findAndReplacePattern(String[] words, String pattern) {
11 List<String> matchedWords = new ArrayList<>();
12 // Iterate through each word in the array
13 for (String word : words) {
14 // If the word matches the pattern, add it to the result list
15 if (doesWordMatchPattern(word, pattern)) {
16 matchedWords.add(word);
17 }
18 }
19 return matchedWords;
20 }
21
22 /**
23 * Checks if the given word matches the given pattern.
24 *
25 * @param word the word to match against the pattern
26 * @param pattern the pattern to be matched with the word
27 * @return true if the word matches the pattern; false otherwise
28 */
29 private boolean doesWordMatchPattern(String word, String pattern) {
30 // Arrays to keep track of character mappings for both the word and the pattern
31 int[] wordToPatternMapping = new int[128];
32 int[] patternToWordMapping = new int[128];
33
34 // Iterate through characters of the word and the pattern simultaneously
35 for (int i = 0; i < word.length(); ++i) {
36 char wordChar = word.charAt(i);
37 char patternChar = pattern.charAt(i);
38
39 // If current mapping does not match, return false (patterns do not match)
40 if (wordToPatternMapping[wordChar] != patternToWordMapping[patternChar]) {
41 return false;
42 }
43
44 // Update the mappings (using i+1 to avoid default 0 value of int array)
45 wordToPatternMapping[wordChar] = i + 1;
46 patternToWordMapping[patternChar] = i + 1;
47 }
48 // If all characters matched the pattern, return true
49 return true;
50 }
51}
52
1#include <string>
2#include <vector>
3
4class Solution {
5public:
6 // findAndReplacePattern finds all the words that match the given pattern.
7 // @param words: a list of strings representing the words to be matched.
8 // @param pattern: a string representing the pattern to match.
9 // @return: a list of strings that match the pattern.
10 vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
11 vector<string> matchingWords; // Will hold the words that match the pattern.
12
13 // Lambda function to check if a word matches the pattern.
14 auto isMatch = [](const string& word, const string& pattern) {
15 int wordToPatternMapping[128] = {0}; // Maps characters in word to pattern.
16 int patternToWordMapping[128] = {0}; // Maps characters in pattern to word.
17
18 // Loop through the characters in the words and pattern.
19 for (int i = 0; i < word.size(); ++i) {
20 // Check if current mapping does not match.
21 if (wordToPatternMapping[word[i]] != patternToWordMapping[pattern[i]])
22 return false; // The words do not follow the same pattern so return false.
23
24 // Update the mappings to reflect the most recent character mapping.
25 wordToPatternMapping[word[i]] = i + 1;
26 patternToWordMapping[pattern[i]] = i + 1;
27 }
28 // The full word matches the pattern.
29 return true;
30 };
31
32 // Check each word in the list to see if it matches the pattern.
33 for (const auto& word : words) {
34 if (isMatch(word, pattern))
35 matchingWords.emplace_back(word); // Add word to list if it matches the pattern.
36 }
37
38 return matchingWords; // Return the list of matching words.
39 }
40};
41
1// Function to find all words that match the given pattern
2function findAndReplacePattern(words: string[], pattern: string): string[] {
3 // Filter the words array to include only the words that match the pattern
4 return words.filter((word) => {
5 // Initialize two maps to store the character to index mappings for the word and pattern
6 const wordToPatternMap = new Map<string, number>();
7 const patternToWordMap = new Map<string, number>();
8
9 // Iterate over each character in the word
10 for (let i = 0; i < word.length; i++) {
11 // Check if there is a mismatch between the current mappings of the word and pattern
12 if (wordToPatternMap.get(word[i]) !== patternToWordMap.get(pattern[i])) {
13 // If a mismatch is found, exclude this word
14 return false;
15 }
16 // Update the mappings with the current index
17 wordToPatternMap.set(word[i], i);
18 patternToWordMap.set(pattern[i], i);
19 }
20
21 // If all characters have been mapped successfully, include this word
22 return true;
23 });
24}
25
Time and Space Complexity
The time complexity of the function findAndReplacePattern
is O(N * K)
, where N
is the length of the words
list and K
is the length of each word (and the pattern). This is because for each of the N
words, the function match
is called, which iterates over the entire length K
of the word and the pattern once.
The space complexity is O(1)
since we only use two fixed-size arrays m1
and m2
of size 128 (the number of ASCII characters). The size of these arrays does not scale with the input size, thus it is constant.
Learn more about how to find time and space complexity quickly using problem constraints.
Which technique can we use to find the middle of a linked list?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!