https://leetcode.com/problems/unique-word-abbreviation/
Unique Word Abbreviation
Total Accepted: 984 Total Submissions: 5829 Difficulty: Easy
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
Code:
class ValidWordAbbr(object):
def __init__(self, dictionary):
"""
initialize your data structure here.
:type dictionary: List[str]
"""
self.c2k = lambda s: s[0] + str(len(s)-2) + s[-1]
ab = [(self.c2k(s), s) for s in dictionary]
d = dict()
for k,v in ab:
if not d.get(k):
d[k] = set()
d[k].add(v)
self.d = d
def isUnique(self, word):
"""
check if a word is unique.
:type word: str
:rtype: bool
"""
key = self.c2k(word)
if not self.d.get(key):
return True
else:
if word in self.d[key] and len(self.d[key])==1:
return True
return False
# Your ValidWordAbbr object will be instantiated and called as such:
# vwa = ValidWordAbbr(dictionary)
# vwa.isUnique("word")
# vwa.isUnique("anotherWord")
Idea:
You build a dictionary first in which key is every word first letter and last letter plus the length between them. Then a word (transformed into first letter+length+last letter) is unique if:
1. the dictionary doesn’t have the word as key at all
2. the dictionary has the word as key. But the value corresponding to the key is a set only containing the word. That means, the current word is the only word with same transformation in dictionary.