Add and Search Word - Data structure design


#1

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.

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.


#2

We use a Trie to store the words and use recursion to find out if a given word or regular expression exists in our data structure.

The search function uses a match func which does 2 things.

  1. If the current character is not a . then it continues the search with the matching children of the current node.
  2. If it is a . we basically check if any of the all available nodes at the current node gets the result. this basically calls the match function for every children present.
type TrieNode struct{
    item string
    children []*TrieNode
}

type WordDictionary struct {
    root *TrieNode
}


/** Initialize your data structure here. */
func Constructor() WordDictionary {
    root := new(TrieNode)
    root.children = make([]*TrieNode, 26)
    return WordDictionary{root: root}
}


/** Adds a word into the data structure. */
func (this *WordDictionary) AddWord(word string)  {
    temp := this.root
    for _, ch := range word{
        if temp.children[ch-'a']==nil{
            temp.children[ch-'a']=&TrieNode{children:make([]*TrieNode, 26)}
        }
        temp = temp.children[ch-'a']
    }
    temp.item = word
}


/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
func (this *WordDictionary) Search(word string) bool {
    return match([]rune(word), 0, this.root)
}

func match(word []rune, index int, node *TrieNode) bool {
    if(index==len(word)){
        return node.item!=""
    }
    if word[index]!='.'{
        return node.children[word[index]-'a']!=nil && match(word, index+1, node.children[word[index]-'a'])
    } else {
        for i := range node.children{
            if node.children[i]!=nil{
                if(match(word, index+1, node.children[i])){
                    return true
                }
            }
        }
    }
    return false
}


/**
 * Your WordDictionary object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddWord(word);
 * param_2 := obj.Search(word);
 */