【哈希表】查找和替换模式

题目

890. 查找和替换模式

---

你有一个单词列表 words 和一个模式 pattern，你想知道 words 中的哪些单词与模式匹配。

如果存在字母的排列 p ，使得将模式中的每个字母 x 替换为 p(x) 之后，我们就得到了所需的单词，那么单词与模式是匹配的。

（回想一下，字母的排列是从字母到字母的双射：每个字母映射到另一个字母，没有两个字母映射到同一个字母。）

返回 words 中与给定模式匹配的单词列表。

你可以按任何顺序返回答案。

示例：

输入：words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
输出：["mee","aqq"]
解释：
"mee" 与模式匹配，因为存在排列 {a -> m, b -> e, ...}。
"ccc" 与模式不匹配，因为 {a -> c, b -> c, ...} 不是排列。
因为 a 和 b 映射到同一个字母。

提示：

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

Constraints:

• 1 <= pattern.length <= 20
• 1 <= words.length <= 50
• words[i].length == pattern.length
• pattern and words[i] are lowercase English letters

解题

方法一：哈希表

思路

维护两组映射：目标字符 -> 模板字符 和 模板字符 -> 目标字符

边遍历边更新映射，如果某次遍历中发现 目标字符已经对应了与当前模板字符不同的字符 或者 模板字符已经对应了与当前目标字符不同的字符，就说明该字符串不符合匹配模式，直接跳过该字符串去验证下一个字符串。

代码

class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> ans = new ArrayList<>();
        int n = pattern.length();
        char[] pArr = pattern.toCharArray();
        outer: for (String word : words) {
            Map<Character, Character> map = new HashMap<>();
            Map<Character, Character> map1 = new HashMap<>();
            for (int i = 0; i < n; i++) {
                Character ch = map.put(word.charAt(i), pArr[i]);
                Character ch1 = map1.put(pArr[i], word.charAt(i));
                if (ch != null && ch != pArr[i] ||
                    ch1 != null && ch1 != word.charAt(i)) continue outer;
            }
            ans.add(word);
        }
        return ans;
    }
}

优化

由于只会出现小写字母，使用数组代替哈希表。

class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> ans = new ArrayList<>();
        int n = pattern.length();
        char[] pArr = pattern.toCharArray();
        outer: for (String word : words) {
            int[] map1 = new int[27];
            int[] map2 = new int[27];
            for (int i = 0; i < n; i++) {
                char c = word.charAt(i), p = pArr[i];
                int ck = c - 'a' + 1, pk = p - 'a' + 1;
                if (map1[ck] == 0) map1[ck] = p;
                if (map2[pk] == 0) map2[pk] = c;
                if (map1[ck] != p || map2[pk] != c) continue outer;
            }
            ans.add(word);
        }
        return ans;
    }
}