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
(1) Java
class ValidWordAbbr {
private Map<String, String> map = new HashMap<>();
public ValidWordAbbr(String[] dictionary) {
for(String str : dictionary) {
if(str.length() < 3) {
map.put(str, str);
} else {
String key = getKey(str);
if (map.containsKey(key)) {
map.put(key, "");
} else {
map.put(key, str);
}
}
}
}
public boolean isUnique(String word) {
String key = word;
if (word.length() >= 3) {
key = getKey(word);
}
return !map.containsKey(key) || map.get(key).equals(word);
}
private String getKey(String str) {
StringBuilder sb = new StringBuilder();
sb.append(str.charAt(0)).append(str.length()-2).append(str.charAt(str.length()-1));
return sb.toString();
}
}
/**
* Your ValidWordAbbr object will be instantiated and called as such:
* ValidWordAbbr obj = new ValidWordAbbr(dictionary);
* boolean param_1 = obj.isUnique(word);
*/
(2) Python
class ValidWordAbbr:
def __init__(self, dictionary):
"""
:type dictionary: List[str]
"""
self.abdict = collections.defaultdict(set)
for string in dictionary:
if len(string) < 3:
self.abdict[string].add(string)
else:
sub = string[0]+str(len(string)-2)+string[-1]
self.abdict[sub].add(string)
def isUnique(self, word):
"""
:type word: str
:rtype: bool
"""
sub = word
if len(word) >= 3:
sub = word[0]+str(len(word)-2)+word[-1]
if not word in self.abdict[sub] and len(self.abdict[sub])==0:
return True
if word in self.abdict[sub] and len(self.abdict[sub])==1:
return True
return False
# Your ValidWordAbbr object will be instantiated and called as such:
# obj = ValidWordAbbr(dictionary)
# param_1 = obj.isUnique(word)
(3) Scala