leetcode 890. Find and Replace Pattern（查找和替换pattern)

Given a list of strings words and a string pattern, return a list of words[i] that match pattern. You may return the answer in any order.

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.

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”]

返回words中和pattern匹配的单词list。
和pattern匹配是指对应的字母匹配。多个字母不能同时匹配一个字母。

思路：
可以用hashmap保存映射关系，但是看到了一个更简洁的方法。

从左到右遍历单词的字母时，如果匹配到了pattern的一个字母，
比如mee和pattern “abb”
m和a匹配，第一个e和第一个b匹配，它们的index是相同的；
那么到了后面的e时，找到它出现的第一个index, 一定和b出现的第一个index一样，
这个index相同就相当于在hashmap中找到了对应关系。

用index模拟hashmap, 这样就不需要另存一个hashmap.

public List<String> findAndReplacePattern(String[] words, String pattern) {
    
    List<String> res = new ArrayList<>();
    
    for(String word : words) {
    
        if(check(word, pattern)) res.add(word);
    }
    return res;
}

boolean check(String word, String pattern) {
    
    for(int i = 0; i < word.length(); i++) {
    
        if(word.indexOf(word.charAt(i)) != pattern.indexOf(pattern.charAt(i))) return false;
    }
    return true;
}