Add and Search Word - Data structure design

Problem: Add and Search Word - Data structure design

I use a trie to solve the problem, as what the hints say. However, there's other faster solution using hash table.

Code in Python:

class TrieNode(object):
    def __init__(self):
        self.isWord = False
        self.children = [None] * 26

class Trie(object):
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for c in word:
            if not node.children[ord(c)-ord('a')]:
                node.children[ord(c)-ord('a')] = TrieNode()
            node = node.children[ord(c)-ord('a')]
        node.isWord = True

class WordDictionary(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.trie = Trie()

    def addWord(self, word):
        """
        Adds a word into the data structure.
        :type word: str
        :rtype: void
        """
        self.trie.insert(word)


    def search(self, word):
        """
        Returns if the word is in the data structure. A word could
        contain the dot character '.' to represent any one letter.
        :type word: str
        :rtype: bool
        """
        return self.search_helper(self.trie.root, word)

    def search_helper(self, node, word):
        if not word:
            if node.isWord: return True
            else: return False
        if word[0] == '.':
            for child in node.children:
                if child and self.search_helper(child, word[1:]): return True
            return False
        else:
            if node.children[ord(word[0])-ord('a')]: return self.search_helper(node.children[ord(word[0])-ord('a')], word[1:])
            else: return False

results matching ""

    No results matching ""