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?