288. Unique Word Abbreviation

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

Solution:

To clarify the problem, we take a look at these examples:

[“dog”]; isUnique(“dig”);
False.
Because "dig" has the same abbreviation with "dog" and dog is already in the dictionary.

[“dog”, “dog"]; isUnique(“dog”);
True.
Because "dog" is the only abbreviation of "dog".

[“dog”, “dig”]; isUnique(“dog”);
False.
Because "dog" had "dig" have the same abbreviation.

To convert a word to its abbreviation, we first check if the length of the word is smaller or equal to 2.

If so, we do not need to convert it.

Otherwise, the abbreviation is the word's first letter + its length - 2 + the word's last letter.

We use a HashMap to store the abbreviation to word mapping.

If we find an abbreviation can map to two different words, we simply set the word to "".

When we check if a word is valid, we check whether its abbreviation's mapping word is itself, or there is no mapping in the HashMap.



Code:

public class ValidWordAbbr {

    public HashMap<String, String> map;
    public ValidWordAbbr(String[] dictionary) {
        map = new HashMap<>();
        for (String word : dictionary) {
            String abbr = getAbbr(word);
            if (!map.containsKey(abbr)) {
                map.put(abbr, word);
            }
            else {
                if (!map.get(abbr).equals(word)) {
                    map.put(abbr, "");
                }
            }
        }
    }
    
    public boolean isUnique(String word) {
        String abbv = getAbbr(word);
        return !map.containsKey(abbv) || map.get(abbv).equals(word);
    }
    
    public String getAbbr(String word) {
        int n = word.length();
        return n <= 2 ? word : "" + word.charAt(0) + (n - 2) + word.charAt(n - 1);
    }
}

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