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).