Since the input set is small and the character set is finite, it is acceptable to enumerate through all possible combinations and see if the new word exists in the dictionary and the time complexity for search is O(k^2) where k is the length of the word.
Funnily enough, the comment in the skeleton for the
search method already hints at using a "trie" but it's not needed to pass the contest.
By Yang Shun
class MagicDictionary(object): def __init__(self): self.words = None def buildDict(self, dict): self.words = set(dict) def search(self, word): chars = set(word) for index, char in enumerate(word): for i in range(26): sub = chr(ord('a') + i) if sub == char: continue new_word = word[:index] + sub + word[index + 1:] if new_word in self.words: return True return False
This is not O(k). It's O(k^2) because it's taking C * k at each char in 'word' due to the substring generation. Thus the algorithm will perform C * k operations for k characters == O(k^2)
@Ellest You're right, I missed that out. Have edited the answer to account for that. Thanks for pointing it out (:
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.