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

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.

Note:

1 <= words.length <= 50
1 <= pattern.length = words[i].length <= 20

自己解法，原来采用两个map记录对应关系，所有不是对应关系都视为错误

class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        HashMap check1 = new HashMap();
        HashMap check2 = new HashMap();
        char[] pat = pattern.toCharArray();
        char[] chars;
        List ret = new ArrayList();
        boolean find = true;
        for (String word : words) {
            chars = word.toCharArray();
            check1.clear();
            check2.clear();
            find = true;
            for (int i = 0; i < chars.length; i++) {
                if(check1.containsKey(chars[i])){

                    if(!check1.get(chars[i]).equals(pat[i])){
                        find =false;
                        break;
                    }

                }else if(check2.containsKey(pat[i])){
                    if(!check2.get(pat[i]).equals(chars[i])){
                        find =false;
                        break;
                    }
                }else{
                    check1.put(chars[i],pat[i]);
                    check2.put(pat[i],chars[i]);
                }
            }
            if(find){
                ret.add(word);
            }
        }
        return ret;
    }
}

官方解法：two Map，跟我自己想法保持一致

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

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

官方解法：one Map，一个Map从速度和空间都没有比第一种快。

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

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

两种官方答案都跟我一样是2ms，没有超过90%。

速度超越100%的解法，快过官方解法。
本文利用字母的ascii码的顺序，利用两个整数数组实现两个Map的效果。速度肯定比map要快

class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> res = new ArrayList<>();
        for(String word: words) {
            if(isValid(word, pattern)) res.add(word);
        }
        return res;
    }
    
    private boolean isValid(String word, String pattern) {
        if(word.length() != pattern.length()) return false;
        int[] w = new int[26];
        int[] p = new int[26];
        for(int i = 0; i < word.length(); ++i) {
            int idx1 = word.charAt(i) - 'a';
            int idx2 = pattern.charAt(i) - 'a';
            if(w[idx1] != p[idx2]) return false;
            w[idx1] = p[idx2] = i + 1;
        }
        
        return true;
    }
}