Scale Engineer

Find and Replace Pattern

Med
#0844Time: O(N * K^2), where `N` is the number of words and `K` is the length of the pattern. For each of the `N` words, we iterate `K` times. Inside the loop, `map.containsValue()` takes `O(K)` time in the worst case, leading to a total of `O(K^2)` for the `isMatch` function.Space: O(1) auxiliary space. The map stores at most 26 key-value pairs, which is constant.1 company
Data structures
ArrayHash TableString
Companies
Zomato

Prompt

Given a list of strings words and a string pattern, return a list of words[i] that match pattern. You may return the answer in any order.

A word matches the pattern if there exists a permutation of letters p so that after replacing every letter x in the pattern with p(x), we get the desired word.

Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.

 

Example 1:

Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]
Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}. 
"ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation, since a and b map to the same letter.

Example 2:

Input: words = ["a","b","c"], pattern = "a"
Output: ["a","b","c"]

 

Constraints:

  • 1 <= pattern.length <= 20
  • 1 <= words.length <= 50
  • words[i].length == pattern.length
  • pattern and words[i] are lowercase English letters.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach iterates through each word and compares it with the pattern character by character. A single hash map is used to maintain the mapping from pattern characters to word characters. For a word to match, two conditions must be met for every character pair (pattern[i], word[i]):

  1. If pattern[i] is already in the map, its mapped value must be word[i].
  2. If pattern[i] is not in the map, we must ensure word[i] has not been mapped to by any other pattern character. This is checked by searching through all values in the map.

Algorithm

    1. Initialize an empty list result.
    1. For each word in the input words array:
    1. Call a helper function isMatch(word, pattern).
    1. Inside isMatch, create a single HashMap to store mappings from pattern characters to word characters.
    1. Iterate through the pattern and word from left to right.
    1. For each character p from pattern and w from word:
    1. If `p` is a key in the map, check if its value is `w`. If not, return `false`. 
    1. If `p` is not a key, check if `w` exists as a value in the map using `containsValue()`. If it does, return `false`.
    1. If both checks pass, add the mapping `p -> w` to the map.
    1. If the loop completes, return true.
    1. If isMatch returns true, add the word to the result list.
    1. Return result.

Walkthrough

The main function iterates through the words array. For each word, it calls a helper function isMatch(word, pattern). The isMatch function uses one HashMap<Character, Character>. It iterates from i = 0 to pattern.length() - 1. At each position i, it gets pChar = pattern.charAt(i) and wChar = word.charAt(i). If map.containsKey(pChar), it checks if map.get(pChar) equals wChar. If not, it's a mismatch, and it returns false. If !map.containsKey(pChar), it checks if map.containsValue(wChar). This check is the bottleneck, as it requires iterating through the map's values, taking time proportional to the number of entries in the map. If wChar is already a value, it violates the one-to-one mapping rule, so it returns false. If both checks pass, a new mapping is added: map.put(pChar, wChar). If the loop finishes, the word is a match.

class Solution {    public List<String> findAndReplacePattern(String[] words, String pattern) {        List<String> result = new ArrayList<>();        for (String word : words) {            if (isMatch(word, pattern)) {                result.add(word);            }        }        return result;    }     private boolean isMatch(String word, String pattern) {        Map<Character, Character> map = new HashMap<>();        for (int i = 0; i < pattern.length(); i++) {            char pChar = pattern.charAt(i);            char wChar = word.charAt(i);            if (map.containsKey(pChar)) {                if (map.get(pChar) != wChar) {                    return false;                }            } else {                // This is the inefficient part                if (map.containsValue(wChar)) {                    return false;                }                map.put(pChar, wChar);            }        }        return true;    }}

Complexity

Time

O(N * K^2), where `N` is the number of words and `K` is the length of the pattern. For each of the `N` words, we iterate `K` times. Inside the loop, `map.containsValue()` takes `O(K)` time in the worst case, leading to a total of `O(K^2)` for the `isMatch` function.

Space

O(1) auxiliary space. The map stores at most 26 key-value pairs, which is constant.

Trade-offs

Pros

  • Conceptually simple to understand.

Cons

  • Inefficient due to the O(K) containsValue check inside the main loop, leading to a quadratic time complexity relative to the string length.

Solutions

class Solution {public  List<String> findAndReplacePattern(String[] words, String pattern) {    List<String> ans = new ArrayList<>();    for (String word : words) {      if (match(word, pattern)) {        ans.add(word);      }    }    return ans;  }private  boolean match(String s, String t) {    int[] m1 = new int[128];    int[] m2 = new int[128];    for (int i = 0; i < s.length(); ++i) {      char c1 = s.charAt(i);      char c2 = t.charAt(i);      if (m1[c1] != m2[c2]) {        return false;      }      m1[c1] = i + 1;      m2[c2] = i + 1;    }    return true;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem