LeetCode 890 - Find and Replace Pattern

https://leetcode.com/articles/find-and-replace-pattern/

You have a list of words and a pattern, and you want to know which words in words matches the pattern.

A word matches the pattern if there exists a permutation of letters p so that after replacing every letter xin 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.)

Return a list of the words in words that match the given pattern. 

You may return the answer in any order.

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.

Approach 1: Two Maps

Intuition and Algorithm

If say, the first letter of the pattern is "a", and the first letter of the word is "x", then in the permutation, "a" must map to "x".

We can write this bijection using two maps: a forward map $\text{m1}$ and a backwards map $\text{m2}$.

$\text{m1} : \text{"a"} \rightarrow \text{"x"}$

$\text{m2} : \text{"x"} \rightarrow \text{"a"}$

Then, if there is a contradiction later, we can catch it via one of the two maps. For example, if the (word, pattern) is ("aa", "xy"), we will catch the mistake in $\text{m1}$ (namely, $\text{m1}(\text{"a"}) = \text{"x"} = \text{"y"}$). Similarly, with (word, pattern) = ("ab", "xx"), we will catch the mistake in $\text{m2}$.

    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;
    }

    public boolean match(String word, String pattern) {
        Map<Character, Character> m1 = new HashMap();
        Map<Character, Character> m2 = new HashMap();

        for (int i = 0; i < word.length(); ++i) {
            char w = word.charAt(i);
            char p = pattern.charAt(i);
            if (!m1.containsKey(w)) m1.put(w, p);
            if (!m2.containsKey(p)) m2.put(p, w);
            if (m1.get(w) != p || m2.get(p) != w)
                return false;
        }

        return true;
    }

As in Approach 1, we can have some forward map $\text{m1} : \mathbb{L} \rightarrow \mathbb{L}$, where $\mathbb{L}$ is the set of letters.

However, instead of keeping track of the reverse map $\text{m2}$, we could simply make sure that every value $\text{m1}(x)$ in the codomain is reached at most once. This would guarantee the desired permutation exists.

So our algorithm is this: after defining $\text{m1}(x)$ in the same way as Approach 1 (the forward map of the permutation), afterwards we make sure it reaches distinct values.

    public boolean match(String word, String pattern) {

        Map<Character, Character> M = new HashMap();

        for (int i = 0; i < word.length(); ++i) {

            char w = word.charAt(i);

            char p = pattern.charAt(i);

            if (!M.containsKey(w)) M.put(w, p);

            if (M.get(w) != p) return false;

        }

        boolean[] seen = new boolean[26];

        for (char p: M.values()) {

            if (seen[p - 'a']) return false;

            seen[p - 'a'] = true;

        }

        return true;

    }

X. https://leetcode.com/problems/find-and-replace-pattern/discuss/161288/C%2B%2BJavaPython-Normalise-Word

Normalise a string to a standard pattern.
Yes. You can pass the F(pattern) to the sub function and return earlier in case of dismatch.

    public List<String> findAndReplacePattern(String[] words, String pattern) {
        int[] p = F(pattern);
        List<String> res = new ArrayList<String>();
        for (String w : words)
            if (Arrays.equals(F(w), p)) res.add(w);
        return res;
    }

    public int[] F(String w) {
        HashMap<Character, Integer> m = new HashMap<>();
        int n = w.length();
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            m.putIfAbsent(w.charAt(i), m.size());
            res[i] = m.get(w.charAt(i));
        }
        return res;
    }