Checking unique words and their abbreviations

Question

In an attempt to solve a problem on Leetcode, I used dictionary and sets to have O(1) time complexity.

However, my speed is too slow, better than just the 5% of Python submissions.

Here is my code:

from typing import List


class ValidWordAbbr:

    def __init__(self, dictionary: List[str]):
        self.dictionary = dictionary
        self.dictionary_abbn = {}
        self.abbn_set = set()
        for key in self.dictionary:
            if len(key) <= 2:
                self.dictionary_abbn[key] = key
                continue
            abbn = '{}{}{}'.format(key[0], len(key)-2, key[-1])
            self.dictionary_abbn[key] = abbn
            self.abbn_set.add(abbn)

    def isUnique(self, word: str) -> bool:
        abbn = word if len(word) <= 2 else '{}{}{}'.format(
            word[0], len(word)-2, word[-1])
        if abbn not in self.abbn_set:
            return True
        for key in self.dictionary_abbn.keys():
            if key != word and self.dictionary_abbn[key] == abbn:
                return False
        return True

How can I improve the runtime?

Answer 1

Variable names

I assume that your dictionary: List refers to an English dictionary and not a data-structure dictionary. This is confusing. Consider calling it something like words.

PEP8

isUnique should be is_unique if LeetCode lets you.

Formatting

'{}{}{}'.format is a quite slow method of concatenating three strings in this case. Try instead

''.join((
   key[0],
   str(len(key) - 2),
   key[-1],
))

This should also be factored out into a function since you use it twice.

Define slots

Read about how to do this here:

https://docs.python.org/3/reference/datamodel.html#object.__slots__

Answer 2

This code makes isUnique() O(n), where n is the size of dictionary_abbr:

for key in self.dictionary_abbn.keys():
    if key != word and self.dictionary_abbn[key] == abbn:
        return False

Calculating the abbreviation of a word is O(1), so it doesn't make sense to build a dict mapping words to their abbreviations. However, looking up an abbreviation to find the word could benefit from having a dict to keep that an O(1) operation.

from typing import List

class ValidWordAbbr:

    def __init__(self, words: List[str]):
        self.lookup = defaultdict(list)

        for word in words:
            abbn = self.abbreviate(word)
            self.lookup[abbn].append(word)

    def abbreviate(self, word: str) -> bool:
        return f"{word[0]}{len(word)}{word[-1]}" if len(word) > 2 else word

    def isUnique(self, word: str) -> bool:
        abbn = self.abbreviate(word)

        words = self.lookup.get(abbn, [])

        #it is unique if the there are no words with that abbreviation or
        # there is only 1 word and it's the same as the one being checked
        return len(words) == 0 or len(words) == 1 and word in words