Add and Search Word - Data structure design

Question

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note: You may assume that all words are consist of lowercase letters a-z.

Tags

• Trie
• Hash Table

Thought

Two solutions:

• Trie
• Hash Map

The implementation of trie is straightforward. A new class named Node is defined to represent a node in the trie. The class of WordDictionary represents the whole trie. In all the node of that trie, there are a list of child nodes. The total number of these child nodes is 26 to represent 26 different characters. Another attribute called end_flag is used to represent whether this character is an end of the word.

However, the efficiency of Trie is very low in test cases. Thus, Hash Map is also used to compare their performance with Trie. In the Hash Map, the key of the dictionary is the length of the word, because the character . doesn't change the length of the word. The value of the dictionary is the set of words with the corresponding length.

Code

Use Trie:

class Node:
    def __init__(self):
        """
        Initialize the node for trie here.

        children: the pointer to the child node, default value is None.
        end_flag: the flag to indicate whether this character is an end of a word in the WordDictionary. Default value is False.
        """
        self.children = dict()
        self.end_flag = False


class WordDictionary(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.head = Node()


    def addWord(self, word):
        """
        Adds a word into the data structure.
        :type word: str
        :rtype: void
        """
        ptr = self.head
        for ch in word:
            if ch not in ptr.children:
                ptr.children[ch] = Node()
            ptr = ptr.children[ch]
        ptr.end_flag = True


    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
        """
        def helper(string, root):
            """
            Check whether there is a string existed in the Trie defined with root node
            """
            if root is None:
                return False
            if len(string) == 0:
                return root.end_flag
            ch = string[0]
            if ch != '.':
                return helper(string[1:], root.children.get(ch, None))
            else:
                result = False
                for key in root.children.keys():
                    result |= helper(string[1:], root.children[key])
                return result

        return helper(word, self.head)

Use dictionary and set:

class WordDictionary(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.word_dict = collections.defaultdict(set)


    def addWord(self, word):
        """
        Adds a word into the data structure.
        Use the length as the key
        :type word: str
        :rtype: void
        """
        length = len(word)
        self.word_dict[length].add(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
        """
        length = len(word)
        if not word:
            return False
        if '.' not in word:
            return (word in self.word_dict[length])
        for v in self.word_dict[length]:
            for i, ch in enumerate(word):
                if ch != v[i] and ch != '.':
                    break
                if i == length - 1:
                    return True
        return False