Python solution with detailed explanation


  • 0
    G

    Solution

    Unique Word Abbreviation https://leetcode.com/problems/unique-word-abbreviation/

    Algorithm

    1. Preprocess the dictionary. Key is abbreviation. Value is set of words in dictionary which have this abbreviation.
    2. abbr_new = get_abbr(new_word)
    3. if abbr_new is not in pre-processed dictionary, then the word is unique - return True.
    4. 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[0], 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
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.