> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/hash/jian-guo/unique-word-abbreviation.md).

# Unique Word Abbreviation

<https://leetcode.com/problems/unique-word-abbreviation/description/>

> An abbreviation of a word follows the form \<first letter>\<number>\<last letter>. Below are some examples of word abbreviations:
>
> a) it --> it (no abbreviation)
>
> ```
>  1
> ```
>
> b) d|o|g --> d1g
>
> ```
>           1    1  1
>
>  1---5----0----5--8
> ```
>
> c) i|nternationalizatio|n --> i18n
>
> ```
>           1
>
>  1---5----0
> ```
>
> d) l|ocalizatio|n --> l10n
>
> Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word's abbreviation is unique if no other word from the dictionary has the same abbreviation.
>
> Example:
>
> Given dictionary = \[ "deer", "door", "cake", "card" ]
>
> isUnique("dear") ->
>
> false
>
> isUnique("cart") ->
>
> true
>
> isUnique("cane") ->
>
> false
>
> isUnique("make") ->
>
> true

## Thoughts

这道题题意说的不是很清楚. 首先缩写的意思是只保留首尾两个字母, 中间替换成中间substring的长度. 给一个dict, 问对于任意新给的词word, 它的缩写是否可以由dict中不是word的词缩写而成. 直观的解法就是用一个hashmap, key是缩写, value是对应该缩写的在dict中的词. 然后对word检查缩写是否在map中, 如果在则继续检查set中是否包含word, 如果包含再继续检查除了word外是否还有其它词. 这个流程可以简化, 实际上只要对于一个key有两个不同的在dict中单词与之对应, 那这个key就不再可能是unique了. 基于此想法我们把value变成一个string即可, 如果没有额外的就维持string为那个对应的词, 如果有超过一个的就把value设为"".

## Code

```
class ValidWordAbbr {

    private String abbrev(String word) {
        StringBuilder sb = new StringBuilder();
        if (word.length() > 2) {
            sb.append(word.charAt(0)).append(word.length() - 2).append(word.charAt(word.length() - 1));
        } else {
            sb.append(word);
        }
        return sb.toString();
    }

    Map<String, String> map = new HashMap<>();
    public ValidWordAbbr(String[] dictionary) {
        for (String str : dictionary) {
            String abbr = abbrev(str);
            if (!map.containsKey(abbr)) {
                map.put(abbr, str);
            } else if (!map.get(abbr).equals(str)) {
                map.put(abbr, "");
            }
        }
    }

    public boolean isUnique(String word) {
        String abbr = abbrev(word);
        return !map.containsKey(abbr) || map.get(abbr).equals(word);
    }
}

/**
 * Your ValidWordAbbr object will be instantiated and called as such:
 * ValidWordAbbr obj = new ValidWordAbbr(dictionary);
 * boolean param_1 = obj.isUnique(word);
 */
```

## Analysis

时间复杂度O(N). 空间O(N).