侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-06-12 / 0 评论 / 0 点赞 / 285 阅读 / 685 字
温馨提示:
本文最后更新于 2022-07-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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;
    }
}
0

评论区