890. Find and Replace Pattern

MediumArrayHash TableString
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How many times is a tree node visited in a depth first search?

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:

  1. A helper function match is defined, which takes two strings s (the word from the list) and t (the pattern) and determines whether s matches t.

  2. Two arrays of integers, m1 and m2, 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 of m1 and m2 are set to 0.

  3. The function then iterates through the characters of both the pattern and the word simultaneously using a zip function in Python.

  4. For every pair of characters (a, b) from s and t, their ASCII values are used as indices in m1 and m2.

  5. On each iteration, indexed by i (starting at 1 to avoid the 0 initial values of m1 and m2), it checks if m1[ord(a)] is not equal to m2[ord(b)]. If they are not equal, it means that the current character mapping is not consistent with previous mappings, and hence the function returns False.

  6. 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 in s and t occur later, they must result in the same mapping index, or otherwise, they do not follow the pattern and the function would return False.

  7. After completing the loop, if no inconsistencies are found, the function returns True, signifying that the word s matches the pattern t.

  8. The main function in the Solution class uses a list comprehension that goes through all the words in the given list, applying the match function to each word along with the pattern.

  9. Only those words for which the match function returns True 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Example 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.

  1. Take the first word "xyz" and create two arrays, m1 and m2, initialized to 0.

  2. 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 and m2.

  3. When the first characters 'x' and 'a' are encountered, m1[ord('x')] and m2[ord('a')] are set to 1.

  4. Next, compare 'y' of "xyz" to 'b' of "abb". Since 'b' corresponds to 'y' and it's the first encounter, set m1[ord('y')] and m2[ord('b')] to 2.

  5. Lastly, 'z' is compared to 'b'. Since 'b' is already mapped to 'y', m1[ord('z')] is not equal to m2[ord('b')], which is 2. So, the mapping is inconsistent, and "xyz" does not match "abb".

Repeat the process for the remaining words:

  1. "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".

  2. "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".

  3. "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
Not Sure What to Study? Take the 2-min Quiz：

Which data structure is used to implement priority queue?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 to Algo Cheat Sheet

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫