LeetCode 890. 查找和替换模式(模拟+双哈希表)

---

题目

• 890. 查找和替换模式

解法：模拟+双哈希表

**整体思路：**遍历words，逐个判断每个单词是否与pattern匹配

在逐个判断过程中，使用双map构造从字母到字母的映射，即 word 的每个字母需要映射到 pattern 的对应字母，并且 pattern 的每个字母也需要映射到 word 的对应字母。

class Solution {
    
    public List<String> findAndReplacePattern(String[] words, String pattern) {
    
        List<String> res = new ArrayList<>();
        int n = words.length;
        char[] pcs = pattern.toCharArray();
        for (int i = 0; i < n; i++) {
    
            char[] cs = words[i].toCharArray();
            if (cs.length != pcs.length) {
    
                continue ;
            }
            // pattern -> word
            Map<Character, Character> p2wMap = new HashMap<>();
            // word -> pattern
            Map<Character, Character> w2pMap = new HashMap<>();
            boolean flag = true;
            for (int j = 0; j < cs.length; j++) {
    
                char a = pcs[j], b = cs[j];                
                if (p2wMap.containsKey(a)) {
    
                    if (p2wMap.get(a) != b ) {
    
                        flag = false;
                        break;
                    }                    
                } else {
    
                    p2wMap.put(a, b);
                }     

                if (w2pMap.containsKey(b)) {
    
                    if (w2pMap.get(b) != a) {
    
                        flag = false;
                        break;
                    }
                } else {
    
                    w2pMap.put(b, a);
                }
            }
            if (flag) {
    
                res.add(words[i]);
            }
        }
        return res;
    }
}

• 时间复杂度：O(nm)，其中 n 是数组 words 的长度，m 是 pattern 的长度。对于每个 word 需要 O(m) 的时间检查其是否与 pattern 匹配。

• 空间复杂度：O(m)。哈希表需要 O(m) 的空间

也可以利用字符集大小只有 26，进而使用数组充当哈希表，使用 map 记录具体的映射关系，使用 vis 记录哪些字符已被映射

class Solution {
    
    public List<String> findAndReplacePattern(String[] ws, String pe) {
    
        List<String> ans = new ArrayList<>();
        int[] map = new int[26], vis = new int[26];
        for (String s : ws) {
    
            Arrays.fill(map, -1);
            Arrays.fill(vis, 0);
            boolean ok = true;
            for (int i = 0; i < pe.length() && ok; i++) {
    
                int c1 = s.charAt(i) - 'a', c2 = pe.charAt(i) - 'a';
                if (map[c1] == -1 && vis[c2] == 0) {
    
                    map[c1] = c2; vis[c2] = 1;
                } else if (map[c1] != c2) {
    
                    ok = false;
                }
            }
            if (ok) {
    
                ans.add(s);
            }
        }
        return ans;
    }
}

Reference

• 查找和替换模式

• 简单哈希表模拟题