3
\$\begingroup\$

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?

\$\endgroup\$
2
  • 2
    \$\begingroup\$ It would help to know what the task is. \$\endgroup\$
    – RootTwo
    Jul 14, 2020 at 3:33
  • \$\begingroup\$ So much overhead of classes and function, code's definitely be gonna slow. Those coding sites are not for good looking or beautiful code. \$\endgroup\$ Jul 14, 2020 at 16:52

2 Answers 2

4
\$\begingroup\$

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__

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.