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

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

以为要像处理["abc","bcd","xyz"]一样，累计diff = string.charAt(i) - string.charAt(i - 1);

但是这道题其实和总偏移量没啥关系，abb aqq acc都可以。所以要用匹配

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［一句话思路］：

 s[w.charAt(i)-'a']=p[pattern.charAt(i)-'a']=i+1;一次匹配一对，没匹配上不行

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

控制真假的boolean变量，在计算每个单词之前，要恢复成true的初始状态

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

s[0] = p[9] = 相同的位置坐标，一次匹配一对

［复杂度］：Time complexity: O(n2) Space complexity: O(n)

［算法思想：迭代/递归/分治/贪心］：

［关键模板化代码］：

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

[是否头一次写此类driver funcion的代码] ：

[潜台词] ：

class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        //initialiazation
        List<String> result = new ArrayList<String>();
        
        //for loop for each word
        for (String word : words) {
            boolean match = true;
            int[] w = new int[26]; int[] p = new int[26];
            //for loop for each char
            for (int i = 0; i < word.length(); i++) {
                if (w[word.charAt(i) - 'a'] != p[pattern.charAt(i) - 'a']) {
                    match = false;
                    break;
                }
                
                if (match == true) {
                    w[word.charAt(i) - 'a'] = i + 1;
                    p[pattern.charAt(i) - 'a'] = i + 1;
                }
            }
           if (match == true) result.add(word); 
        }
        
        //return 
        return result;
    }
}

View Code