algoadvance

Leetcode 890. Find and Replace Pattern

Problem Statement

You are given a list of strings words and a string pattern. You want to find all strings in words that match the given pattern. A string matches the pattern if there is a bijection (one-to-one and onto mapping) between a letter in the pattern and a letter in the string.

In other words, for each character in the pattern there’s a unique corresponding character in the string and vice versa.

For example, given the pattern “abb”, the strings “mee” and “aqq” match the pattern, but “ccc” does not.

Example 1:

Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]

Example 2:

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

Constraints:

Clarifying Questions

  1. Q: Can the words and the pattern contain non-lowercase English letters? A: No, as per problem constraints, words and pattern contain only lowercase English letters.

  2. Q: What should be returned if no words match the pattern? A: An empty list should be returned if no words match the pattern.

  3. Q: Should the order of results be maintained as in the input list? A: Yes, results should appear in the same order as they do in the input.

Strategy

To solve this problem, we need to check if there’s a bijection (one-to-one correspondence) between the characters in the pattern and each word. To implement this, we can follow these steps:

  1. Data Structures: Use two hash maps (dictionaries):
    • pattern_to_word: Maps each character in the pattern to a corresponding character in a word.
    • word_to_pattern: Maps each character in the word to a corresponding character in the pattern.
  2. Iterate: For each word in the list:
    • Check the lengths of the word and the pattern. If they are not the same, they cannot match.
    • For each character pair (pattern character, word character):
      • Ensure the mapping in both hash maps is consistent.
      • If any inconsistency is found, break and continue to the next word.
      • If no inconsistency is found for the whole word, add it to the result list.
  3. Edge Cases: Handle edge cases where the lengths do not match or mappings are inconsistent.

Code

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FindAndReplacePattern {
    
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> result = new ArrayList<>();
        
        for (String word : words) {
            if (matchesPattern(word, pattern)) {
                result.add(word);
            }
        }
        
        return result;
    }
    
    private boolean matchesPattern(String word, String pattern) {
        if (word.length() != pattern.length()) {
            return false;
        }
        
        Map<Character, Character> patternToWord = new HashMap<>();
        Map<Character, Character> wordToPattern = new HashMap<>();
        
        for (int i = 0; i < word.length(); i++) {
            char wChar = word.charAt(i);
            char pChar = pattern.charAt(i);
            
            if (patternToWord.containsKey(pChar)) {
                if (patternToWord.get(pChar) != wChar) {
                    return false;
                }
            } else {
                patternToWord.put(pChar, wChar);
            }
            
            if (wordToPattern.containsKey(wChar)) {
                if (wordToPattern.get(wChar) != pChar) {
                    return false;
                }
            } else {
                wordToPattern.put(wChar, pChar);
            }
        }
        return true;
    }
    
    public static void main(String[] args) {
        FindAndReplacePattern solution = new FindAndReplacePattern();
        String[] words = {"abc", "deq", "mee", "aqq", "dkd", "ccc"};
        String pattern = "abb";
        System.out.println(solution.findAndReplacePattern(words, pattern)); // Output: [mee, aqq]
    }
}

Time Complexity

Thus, the overall time complexity is O(n * m).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI