Find and Replace Pattern

Problem Statement

Given a list of word strings and a single pattern string, the task is to identify which words from the list match the provided pattern. Two strings are considered a match if one can morph into the other by a consistent replacement of characters, such that every letter in the pattern maps uniquely to another letter, forming a bijective relationship.

A crucial condition for two strings to match under the given rules is that these replacements form a perfect one-to-one mapping, where each letter in the pattern maps to a unique letter in the word. This means that no two different letters in the pattern should map to the same letter in the potential matching word.

Examples

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.

Approach and Intuition

1. In order to solve this, you need to compare the structure of each word against the pattern. The main idea is to establish a mapping based on the position of characters:

   • If the first occurrence of a character in the pattern is at the same position as the first occurrence of a corresponding character in the word, and this persists for every character and their corresponding pair, then the word matches the pattern.

2. Based on the above point:

   • For every word in the list, create this character-to-character mapping with the pattern.
   • Check for consistency in this mapping throughout the word. If at any point, the mapping diverges (i.e., a single pattern character tries to map to more than one character or vice-versa), discard this word as it doesn't fit the pattern.

3. Store the words that successfully match this mapping criterion and return them as the output. This matching ensures that the permutation of letters is a bijective (one-to-one and onto) function, meeting the problem's requirement that no two letters map to the same target letter.

Examples:

• For the word "mee" and the pattern "abb", we see that first occurrences of 'a' in "abb" and 'm' in "mee" coincide. Similarly, 'b' maps consistently to 'e', hence "mee" matches "abb".
• The word "ccc" against the pattern "abb", however, fails to meet criteria, as different pattern characters ('a' and 'b') map to the same character ('c'), invalidating the bijective requirement.

From these application points, it's clear that the mapping of characters from the pattern to the word (and vice versa) while maintaining the consistency and uniqueness of these mappings forms the core logic of this problem.

Solutions

class Solution {
    public List<String> filterByPattern(String[] phraseArray, String model) {
        List<String> matches = new ArrayList<>();
        for (String phrase: phraseArray)
            if (isMatch(phrase, model))
                matches.add(phrase);
        return matches;
    }

    public boolean isMatch(String phrase, String model) {
        Map<Character, Character> characterMap = new HashMap<>();
        for (int i = 0; i < phrase.length(); ++i) {
            char charFromPhrase = phrase.charAt(i);
            char charFromModel = model.charAt(i);
            if (!characterMap.containsKey(charFromPhrase)) characterMap.put(charFromPhrase, charFromModel);
            if (characterMap.get(charFromPhrase) != charFromModel) return false;
        }

        boolean[] marked = new boolean[26];
        for (char val: characterMap.values()) {
            if (marked[val - 'a']) return false;
            marked[val - 'a'] = true;
        }
        return true;
    }
}