​LeetCode刷题实战288：单词的唯一缩写

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 单词的唯一缩写，我们先来看题面：

https://leetcode-cn.com/problems/unique-word-abbreviation/

假设你有一个字典和一个单词，请你判断该单词的缩写在这本字典中是否唯一。

若单词的缩写在字典中没有任何 其他 单词与其缩写相同，则被称为单词的唯一缩写。

示例

给定 dictionary = [ "deer", "door", "cake", "card" ]
isUnique("dear") -> false
isUnique("cart") -> true
isUnique("cane") -> false
isUnique("make") -> true

解题

一个单词的缩写可以表示成第一个字母+中间字母个数+最后一个字母。给一个单词字典和一个单词，判断这个单词的缩写是唯一的，即字典的单词缩写中没有这个缩写或者有这个缩写但和这个单词是一样的（注意这种情况的处理）。

解法：定义一个函数用来操作缩写单词，对于字典中的所有单词进行缩写并存入另一个哈希表(key为缩写后的单词，value为set)。再对单词进行缩写，然后判断单词的缩写是否在哈希表中出现，如果没出现那肯定是唯一的。如果出现了还要看set里存的是不是只是这个单词，如果有其它单词出现就不是唯一的。

public class ValidWordAbbr {
    Map<String, Set<String>> map;
    public ValidWordAbbr(String[] dictionary) {
        map = new HashMap<>();
        for (String s : dictionary) {
            String abbr = getAbbr(s);
            if (!map.containsKey(abbr)) {
                map.put(abbr, new HashSet<String>());
            }
            map.get(abbr).add(s);
        }
    }
 
    public boolean isUnique(String word) {
        String abbr = getAbbr(word);
        if (!map.containsKey(abbr) || (map.get(abbr).contains(word) && map.get(abbr).size() == 1)) {
            return true;
        }
        return false;
    }
     
    private String getAbbr(String s) {
        if (s.length() < 3) {
            return s;
        }
        int len = s.length();
        return s.substring(0, 1) + (len - 2) + s.substring(len - 1);
    }
}

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。

上期推文：

LeetCode1-280题汇总，希望对你有点帮助！

LeetCode刷题实战281：锯齿迭代器

LeetCode刷题实战282：给表达式添加运算符

LeetCode刷题实战283：移动零

LeetCode刷题实战284：顶端迭代器

LeetCode刷题实战285：二叉搜索树中的顺序后继

LeetCode刷题实战286：墙和门

LeetCode刷题实战287：寻找重复数