Unique Word Abbreviation LC解題記錄

NO IMAGE

題目內容

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

這題也是鎖住的,通過率只有15%左右。這讓我不得其解,為啥一道easy級別的題目會有如此低的Pass?是人性的扭曲還是道德的淪喪,美國沒有《走近科學》,只能自己動手寫。

解決思路

這題比較考察洋文水平,掃一眼要求很容易看出,應該把已有的dictionary的縮略詞都縮出來,存到一個地方,剛開始用了個Set。再呼叫isUnique的時候,用目標字串壓縮後和Set裡面的元素做比較。有相同的就返回false,沒有就是true。
但是,
後來出了問題,因為目標詞可能和字典裡面的詞一致,比如字典裡只有有”hello”,呼叫isUnique檢查hello的時候,應該返回true,因為沒有其他詞和h3o一樣了。另外,字典裡面只有兩個hello的時候,也是返回true。所以這題的關鍵點在於『no other word』

code

public class ValidWordAbbr {
Map<String,ArrayList<String>> map = new HashMap<>();
public ValidWordAbbr(String[] dictionary) {
//每個詞都輪一遍
for (String str : dictionary) {
String abrv = abbrev(str);
if (!map.containsKey(abrv)){
ArrayList<String> list = new ArrayList<>();
list.add(str);
map.put(abrv,list);
}
else {
ArrayList<String> list = map.get(abrv);
//這裡的判斷是過濾相同的詞
if (!list.contains(str)) list.add(str);
map.put(abrv, list);
}
}
}
public boolean isUnique(String word) {
String abrv = abbrev(word);
if (map.containsKey(abrv)){
//先看相同壓縮串是不是代表多個詞,一旦多了那肯定不行
if (map.get(abrv).size() > 1) return false;
//如果只有1個,那就對比一下這兩個詞是不是一樣的,一樣就行
else if (map.get(abrv).get(0).equals(word)) return true;
return false;
}
//其他情況肯定是都行。
return true;
}
//把字串變成壓縮串
public String abbrev(String word){
if(word == null || word.length() < 3){
return word;
}
//把頭,數字,尾巴連起來。
StringBuilder sb = new StringBuilder();
int len = word.length()-2;
String slen = String.valueOf(len);
sb.append(word.charAt(0));
sb.append(slen);
sb.append(word.charAt(word.length()-1));
return sb.toString();
}
//做測試用
public static void main(String[] args) {
String[] test = {"hello", "a", "a"};
ValidWordAbbr vwa = new ValidWordAbbr(test);
System.out.print(vwa.isUnique("a"));
}
}

複雜度分析

截至目前,我還不太清楚這種設計題會不會特別在意複雜度,可能更注重corner case。這題遍歷一遍字典就可以了,所以複雜度是O(n)。需要注意的是no other word這個說法,讓我多付出了兩次submit的代價,不過還好比15%高一些。

最後再說兩句

距離上一篇文章過了一段時間了,這段時間搬家再適應新環境,解決心理問題。從這一篇開始將會繼續保持更新進度。