Python short solution using defaultdict with comments.


  • 11
    C
    def __init__(self, dictionary):
        self.dic = collections.defaultdict(set)
        for s in dictionary:
            val = s
            if len(s) > 2:
                s = s[0]+str(len(s)-2)+s[-1]
            self.dic[s].add(val)
    
    def isUnique(self, word):
        val = word 
        if len(word) > 2:
            word = word[0]+str(len(word)-2)+word[-1]
        # if word abbreviation not in the dictionary, or word itself in the dictionary (word itself may 
        # appear multiple times in the dictionary, so it's better using set instead of list)
        return len(self.dic[word]) == 0 or (len(self.dic[word]) == 1 and val == list(self.dic[word])[0])

  • 0

    defaultdict is really powerful :-) I try to write it using simple dict and it meets the Time Limit Exceeded...

    class ValidWordAbbr(object):
        def __init__(self, dictionary):
            """
            initialize your data structure here.
            :type dictionary: List[str]
            """
            self.dt = {}
            for d in dictionary:
                abbr = d[0] + str(len(d)) + d[-1]
                if abbr not in self.dt.keys():
                    self.dt[abbr] = set([])
                self.dt[abbr].add(d)
    
        def isUnique(self, word):
            """
            check if a word is unique.
            :type word: str
            :rtype: bool
            """
            abbr = word[0] + str(len(word)) + word[-1]
            return abbr not in self.dt.keys() or self.dt[abbr] == set([word])

  • 0
    C

    Yes, your implementation is good, after you change if abbr not in self.dt.keys(): to if abbr not in self.dt: it will work. The time complexity of the former one is O(n) while the later one is O(1).


  • 0
    C

    abbr = d[0] + str(len(d)) + d[-1] is much more convenient than my code!


  • 0
    C

    I revised your code using defaultdict, this one is much shorter than mine:

    def __init__(self, dictionary):
        self.dt = collections.defaultdict(set)
        for d in dictionary:
            abbr = d[0] + str(len(d)) + d[-1]
            self.dt[abbr].add(d)
    
    def isUnique(self, word):
        abbr = word[0] + str(len(word)) + word[-1]
        return abbr not in self.dt or self.dt[abbr] == set([word])

  • 0

    Hi, caikehe. Great thanks for your detailed reply. I finally have a working version using Python dict :-)


  • 0

    Changed the value of your abbr (to a tuple) and simplified the return line.

    def __init__(self, dictionary):
        self.dt = collections.defaultdict(set)
        for d in dictionary:
            abbr = d[0], len(d), d[-1]
            self.dt[abbr].add(d)
    
    def isUnique(self, word):
        abbr = word[0], len(word), word[-1]
        return self.dt[abbr] <= {word}
    

    Though this can create extra entries if asked about the uniqueness of words not in the dictionary. And the tuple is probably less efficient than the string. But I find it nice anyway.


  • 0
    C

    return self.dt[abbr] <= {word}, this line is nice~


  • 0
    O

    Gosh, it's my first time to find that I don't even know which operator would do what for set. Thanks for sharing!


  • 0
    A

    @StefanPochmann

    Added two lines to make it pass rather frivolous test cases.

    class ValidWordAbbr(object):
        def __init__(self, dictionary):
            self.dt = collections.defaultdict(set)
            for d in dictionary:
                if d:
                    abbr = d[0], len(d), d[-1]
                    self.dt[abbr].add(d)
    
        def isUnique(self, word):
            if not word:
                return True
                
            abbr = word[0], len(word), word[-1]
            return self.dt[abbr] <= {word}
    

Log in to reply
 

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