侧边栏壁纸
博主头像
GabrielxD

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

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【哈希表】单词的唯一缩写

GabrielxD
2022-07-01 / 0 评论 / 0 点赞 / 50 阅读 / 787 字 / 正在检测是否收录...

题目

288. 单词的唯一缩写


单词的 缩写 需要遵循 <起始字母><中间字母数><结尾字母> 这样的格式。如果单词只有两个字符,那么它就是它自身的 缩写 。

以下是一些单词缩写的范例:

  • dog --> d1g 因为第一个字母 'd' 和最后一个字母 'g' 之间有 1 个字母
  • internationalization --> i18n 因为第一个字母 'i' 和最后一个字母 'n' 之间有 18 个字母
  • it --> it 单词只有两个字符,它就是它自身的 缩写

实现 ValidWordAbbr 类:

  • ValidWordAbbr(String[] dictionary) 使用单词字典 dictionary 初始化对象

  • boolean isUnique(string word) 如果满足下述任意一个条件,返回 true ;否则,返回 false

    • 字典 dictionary 中没有任何其他单词的 缩写 与该单词 word缩写 相同。
    • 字典 dictionary 中的所有 缩写 与该单词 word缩写 相同的单词都与 word 相同 。

示例:

输入
["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique", "isUnique"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"], ["cake"]]
输出
[null, false, true, false, true, true]

解释
ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]);
validWordAbbr.isUnique("dear"); // 返回 false,字典中的 "deer" 与输入 "dear" 的缩写都是 "d2r",但这两个单词不相同
validWordAbbr.isUnique("cart"); // 返回 true,字典中不存在缩写为 "c2t" 的单词
validWordAbbr.isUnique("cane"); // 返回 false,字典中的 "cake" 与输入 "cane" 的缩写都是 "c2e",但这两个单词不相同
validWordAbbr.isUnique("make"); // 返回 true,字典中不存在缩写为 "m2e" 的单词
validWordAbbr.isUnique("cake"); // 返回 true,因为 "cake" 已经存在于字典中,并且字典中没有其他缩写为 "c2e" 的单词

提示:

  • 1 <= dictionary.length <= 3 * 10^4
  • 1 <= dictionary[i].length <= 20
  • dictionary[i] 由小写英文字母组成
  • 1 <= word <= 20
  • word 由小写英文字母组成
  • 最多调用 5000isUnique

解题

方法一: 哈希表

思路

维护一个哈希表,键是缩写,值是能转成该缩写的单词集合。判断 isUnique 时只要把传入的单词转成缩写再从哈希表中取出对应的单词集合,如果取不到则满足条件一可以返回 true,如果取到了且集合大小为 1 (只有一种对应单词)且该单词与传入单词相同这满足条件二可以返回 true 其他情况下返回 false

代码

class ValidWordAbbr {
    private Map<String, Set<String>> map;

    public ValidWordAbbr(String[] dictionary) {
        map = new HashMap<>();
        for (String s : dictionary) {
            String abbr = getAbbr(s);
            map.putIfAbsent(abbr, new HashSet<>());
            map.get(abbr).add(s);
        }
    }
    
    public boolean isUnique(String word) {
        String abbr = getAbbr(word);
        Set<String> set = map.get(abbr);
        return set == null || set.size() == 1 && set.contains(word);
    }

    private String getAbbr(String word) {
        int n = word.length();
        if (n <= 2) return word;
        return word.charAt(0) + String.valueOf(n - 2) + word.charAt(n - 1);
    }
}
0

评论区