Unique Word Abbreviation

• Easy
• keyword: Map
• 类似:

Question

• 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    // it is one, five, ten, fifteen, and eighteen
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", "happy", "happy" ]

  • isUnique("dear") -> false
  • isUnique("cart") -> true
  • isUnique("cane") -> false
  • isUnique("make") -> true
  • isUnique("happy") -> true ! 这个很重要, 一开始我没有理解, 导致出错!

Idea

• 先读懂题意: 即每一个单词都由首位2个字母加上中间的长度来形成一个缩写. 当然: 如果只有1或2位的单词的缩写就是本身.
• 很重要的是, 题目说了Unique的意义是: 这个字典里的单词的缩写如果和这个单词一样的话, 那么全写也应该一样. 如果字典里面没有该缩写的话也是Unique.

• 于是有了算法:

  map<string, string>
  for string s : dict:
    if map.contains(abbr)
        if map.get(abbr) != s
            map.put(abbr, "")  // 当有多个单词的abbr一样, 那么显然是违反题意, 所以通过将abbr对应为"", 这样match的时候就无法match, 于是返回false了.
    else 
        map.put(abbr, s)
  

• 为了方便起见, 将abbr method单独出来.

Code

public UniqueWordAbbreviation(String[] dictionary) {
    for (String ss : dictionary) {
      String key = abbr(ss);
      if (map.containsKey(key)) {  // 不要写错称ss了!
        if (!map.get(key).equals(ss)) {
          map.put(key, "");  // say: head, huud. then h2d is not a valid key
        }
      }
      else {
        map.put(key, ss);
      }
    }
  }

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

  private String abbr(String s) {
    if (s.length() < 3) return s;
    return s.charAt(0) + Integer.toString('0' + s.length() - 2) + s.charAt(s.length() - 1);
  }

分析

• 空间复杂度是: 使用了Map, 所以O(N).
• 时间复杂度:
  • 在pre-process, 即ctor调用的时候: 遍历一遍整个map, 通过O(1)的containsKey/get/put, 来初始化map.
  • 在实际判断的时候, 只要O(1)的map的api即可判断是否Unique.

思考

• 这题有2个很重要:
  1. 读懂题意! 一开始我以为只要判断字典的缩写是否包含要查的单词, 但就错了.
  2. Map的设计: key是缩写, Value是对应的单词. 然后在发现多个单词对应一个缩写的时候, 通过将其对应的单词设为"", 这样就无法和任何string match了.