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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-and-replace-pattern
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

与pattern模式匹配的字符串word需要符合两点要求：

1. 在pattern中字符相同的位置，在word中也需要相同，比如pattern为abb，word=bcc就符合条件，bcd就不符合，因为第二位和第三位不相同。
2. 题目要求「没有两个字母映射到同一个字母」，因此还是对于pattern为abb，第一位和二三位字符不能相同，所以ccc不符合要求（尽管其符合第一点要求）。

在实现上，先遍历pattern，记录字符相同的下标集合，存储在map中，key为字母，value为该字母在pattern中出现的下标位置，使用list或者set都可。

然后遍历字符串数组，检查map中的每一个list的位置是否字母相同，这是第一点要求。

对于第二点要求，每遍历完一个list，将这些位置的字母添加到一个set中，表示之后不允许再出现，出现的话说明这个word不符合pattern模式。

代码

class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        // 存储pattern中字母相同的下标位置
        Map<Character, List<Integer>> map = new HashMap<>();
        int n = pattern.length();
        for (int i = 0; i < n; i++) {
            char c = pattern.charAt(i);
            map.computeIfAbsent(c, k -> new ArrayList<>()).add(i);
        }
        List<String> ans = new ArrayList<>();
        for (String w : words) {
            boolean flag = true;
            // 用于判断第二点要求
            Set<Character> set = new HashSet<>();
            for (List<Integer> l : map.values()) {
                char c = w.charAt(l.get(0));
                // 不同的下标组使用了同一个字母，即不满足「没有两个字母映射到同一个字母」
                if (set.contains(c)) {
                    flag = false;
                    break;
                }
                for (int i : l) {
                    if (w.charAt(i) != c) {
                        flag = false;
                        break;
                    }
                }
                if (!flag) {
                    break;
                }
                // 将这一组下标对应的字母加入set，之后不可以再出现
                set.add(c);
            }
            if (flag) {
                ans.add(w);
            }
        }
        return ans;
    }
}