288 Unique Word Abbreviation

288. Unique Word Abbreviation

An abbreviation of a word follows the form . 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

分析 & 代码

这是一题非常坑的简单题。

https://discuss.leetcode.com/topic/37254/let-me-explain-the-question-with-better-examples/2

1) [“dog”]; isUnique(“dig”);   
//False, because “dig” has the same abbreviation with “dog" and “dog” is already in the dictionary. It’s not unique.

2) [“dog”, “dog"]; isUnique(“dog”);  
//True, because “dog” is the only word that has “d1g” abbreviation.

3) [“dog”, “dig”]; isUnique(“dog”);   
//False, because if we have more than one word match to the same abbreviation, this abbreviation will never be unique.

这样就能明白了

　思路:

　　建一个Hashmap，key是缩写，value是对应的词，如果对词典进行建立的时候就已经发现重复了，就把value设置成“”

　　对新来的词，如果这个词的缩写在map并且这个词不是那个字典里产生这个词的原词，那么就返回false。

public class ValidWordAbbr {
    Map<String, String> dic;

    public ValidWordAbbr(String[] dictionary) {
        dic = new HashMap<String, String>();
        for(int i = 0; i < dictionary.length; i++) {
            String abb = generateAbb(dictionary[i]);
            if(dic.containsKey(abb) && !dic.get(abb).equals(dictionary[i])) {
                dic.put(abb, "");
            } else {
                dic.put(abb, dictionary[i]);
            }
        }
    }

    private String generateAbb(String s) {
        int len = s.length();
        if(len < 3) {
            return s;
        }
        StringBuilder sb = new StringBuilder();
        sb.append(s.charAt(0));
        sb.append(len - 2);
        sb.append(s.charAt(len - 1));
        return sb.toString();
    }

    public boolean isUnique(String word) {
        String abb = generateAbb(word);
        return !dic.containsKey(abb) || dic.get(abb).equals(word);
    }
}