Add and Search Word - Data structure design


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.


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

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


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 {
        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);