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
Understand the problem:
The question is a little bit tricky.
There are only 2 conditions we return true for isUnique("word")
1. The abbr does not appear in the dict.
2. The abbr is in the dict && the word appears one and only once in the dict.
Code (Java): (WRONG SOLUTION)
public class ValidWordAbbr {
private Map<String, String> map;
public ValidWordAbbr(String[] dictionary) {
this.map = new HashMap<>();
for (String word : dictionary) {
String abbr = toAbbr(word);
if (map.containsKey(abbr)) {
map.put(abbr, "");
} else {
map.put(abbr, word);
}
}
}
public boolean isUnique(String word) {
String abbr = toAbbr(word);
if (!map.containsKey(abbr) || map.get(abbr).equals(word)) {
return true;
} else {
return false;
}
}
private String toAbbr(String s) {
if (s == null || s.length() <= 2) {
return s;
}
int len = s.length() - 2;
String result = s.charAt(0) + "" + len + s.charAt(s.length() - 1);
return result;
}
}
// Your ValidWordAbbr object will be instantiated and called as such:
// ValidWordAbbr vwa = new ValidWordAbbr(dictionary);
// vwa.isUnique("Word");
// vwa.isUnique("anotherWord");
Update on 9/26/15:
The solution above presumes that the dict does not contains duplicates. However, the OJ updates its test case that
Input:["a","a"],isUnique("a")
Output:[false]
Expected:[true]
So the new solution we need to use two dictionaries, one save the abbr format and the other saves the original dict. The value stores the frequencies of each word.
So how to determine if a word is unique in the abbrivation? There are still two cases to consider:
1. If the abbr of the input word does not appear in the abbr dict, return true;
2. If the abbr of the input word DOES appears in the abbr dict, we must make sure the input word is in the dictionary AND the its abbreviation format can only appear once in the abbr dict.
-- Now here comes to the corner case that the dict contains duplicates. In this case, both the dict and abbr dict will store "a", 2. So in this way, a does not appear only once! So the solution to handle this edge case is we must make sure the word freq in the dict and abbr dict is exactly the same. So we can make sure the word has no other duplicated abbrivations in the abbr dict.
Code (Java):
public class ValidWordAbbr {
private Map<String, Integer> abbrDict;
private Map<String, Integer> dict;
public ValidWordAbbr(String[] dictionary) {
abbrDict = new HashMap<>();
dict = new HashMap<>();
for (String word : dictionary) {
if (dict.containsKey(word)) {
int freq = dict.get(word);
dict.put(word, freq + 1);
} else {
dict.put(word, 1);
}
String abbr = abbreviation(word);
if (abbrDict.containsKey(abbr)) {
int freq = abbrDict.get(abbr);
abbrDict.put(abbr, freq + 1);
} else {
abbrDict.put(abbr, 1);
}
}
}
public boolean isUnique(String word) {
if (word == null || word.length() == 0) {
return true;
}
String abbr = abbreviation(word);
if (!abbrDict.containsKey(abbr)) {
return true;
} else {
if (dict.containsKey(word) && dict.get(word) == abbrDict.get(abbr)) {
return true;
}
}
return false;
}
private String abbreviation(String word) {
if (word.length() <= 2) {
return word;
}
StringBuffer sb = new StringBuffer();
sb.append(word.charAt(0));
sb.append(word.length() - 2);
sb.append(word.charAt(word.length() - 1));
return sb.toString();
}
}
Update on 11/9/15:
public class ValidWordAbbr {
private Set<String> uniqueDict;
private Map<String, String> abbrDict;
public ValidWordAbbr(String[] dictionary) {
uniqueDict = new HashSet<>();
abbrDict = new HashMap<>();
for (String word : dictionary) {
if (!uniqueDict.contains(word)) {
String abbr = getAbbr(word);
if (!abbrDict.containsKey(abbr)) {
abbrDict.put(abbr, word);
} else {
abbrDict.put(abbr, "");
}
uniqueDict.add(word);
}
}
}
public boolean isUnique(String word) {
if (word == null || word.length() == 0) {
return true;
}
String abbr = getAbbr(word);
if (!abbrDict.containsKey(abbr) || abbrDict.get(abbr).equals(word)) {
return true;
} else {
return false;
}
}
private String getAbbr(String word) {
if (word == null || word.length() < 3) {
return word;
}
StringBuffer sb = new StringBuffer();
sb.append(word.charAt(0));
sb.append(word.length() - 2);
sb.append(word.charAt(word.length() - 1));
return sb.toString();
}
}
// Your ValidWordAbbr object will be instantiated and called as such:
// ValidWordAbbr vwa = new ValidWordAbbr(dictionary);
// vwa.isUnique("Word");
// vwa.isUnique("anotherWord");
