Unique Word Abbreviation https://leetcode.com/problems/unique-word-abbreviation/
- Preprocess the dictionary. Key is abbreviation. Value is set of words in dictionary which have this abbreviation.
- abbr_new = get_abbr(new_word)
- if abbr_new is not in pre-processed dictionary, then the word is unique - return True.
- if abbr_new is in dictionary and number of words which abbreviate to it are 1 and new_word is the word which abbreviated to it, then return True.
from collections import defaultdict class ValidWordAbbr(object): def __init__(self, dictionary): """ initialize your data structure here. :type dictionary: List[str] """ self.abbr = defaultdict(set) for word in dictionary: self.abbr[self.get_abbr(word)].add(word) def get_abbr(self, word): return word if len(word) <= 2 else "".join([word, str(len(word)-2),word[-1]]) def isUnique(self, word): """ check if a word is unique. :type word: str :rtype: bool """ abbreviation = self.get_abbr(word) if abbreviation not in self.abbr: return True else: if len(self.abbr[abbreviation]) == 1 and word in self.abbr[abbreviation]: return True return False