211.Add and Search Word - Data structure design

Tags: [data_structure], [prefix_tree], [trie], [search]

Com: {fb}

Link: https://leetcode.com/problems/add-and-search-word-data-structure-design/#/description

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 lettersa-zor.. 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.

Solution: Trie (Prefix Tree)

class WordDictionary(object):

    class TreeNode(object):
        def __init__(self, val):
            self.val = val
            self.end_of_word = False
            self.children = []


    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = self.TreeNode('root')


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

        curr = self.root
        for index in xrange(len(word)):
            c = word[index]
            target_index = -1
            for i in xrange(len(curr.children)):
                if curr.children[i].val == c:
                    target_index = i
                    break

            if target_index < 0:
                new_node = self.TreeNode(c)
                if index == len(word) - 1:
                    new_node.end_of_word = True

                curr.children.append(new_node)
                curr = new_node
            else:
                child = curr.children[target_index]
                if index == len(word) - 1:
                    child.end_of_word = True
                curr = child

    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(word, 0, self.root)

    def search_helper(self, word, index, root):
        c = word[index]
        for child in root.children:
            if index == len(word) - 1:
                if child.end_of_word and (c == '.' or c == child.val):
                    return True
            else:
                if c == '.' or c == child.val:
                    if self.search_helper(word, index + 1, child):
                        return True

        return False

# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

Revelation:

• Use iteration to add word.

Solution: Trie (Prefix Tree)

class WordDictionary(object):

    class TreeNode(object):
        def __init__(self, val):
            self.val = val
            self.end_of_word = False
            self.children = []


    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = self.TreeNode('root')


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

    def insert_word(self, word, index, root):
        # base case
        if index >= len(word):
            return

        c = word[index]
        target_index = -1
        for i in xrange(len(root.children)):
            if root.children[i].val == c:
                target_index = i
                break

        if target_index < 0:
            new_node = self.TreeNode(c)
            if index == len(word) - 1:
                new_node.end_of_word = True

            root.children.append(new_node)
            self.insert_word(word, index + 1, new_node)
        else:
            child = root.children[target_index]
            if index == len(word) - 1:
                child.end_of_word = True
            self.insert_word(word, index + 1, child)


    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(word, 0, self.root)

    def search_helper(self, word, index, root):
        c = word[index]
        for child in root.children:
            if index == len(word) - 1:
                if child.end_of_word and (c == '.' or c == child.val):
                    return True
            else:
                if c == '.' or c == child.val:
                    if self.search_helper(word, index + 1, child):
                        return True

        return False

# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

Revelation:

• When we design the Trie (Prefix Tree) node, don't forget the 'end__of__word' flag.

Note:

• Time complexity of initialization = O(1).
• Time complexity of addWord = O(n), n is the length of the word.
• Time complexity of search = O(n), n is the length of the word.
• The number of elements in the node.children is at most 26, assuming we are dealing with English.