Add and Search Word

要点：

1）Search Word的时候，要用递归而不是循环；

code

class trienode {
public:
    char c;
    map<char, trienode*> hash;
    bool isword;
    trienode()
    {
        isword = false;
    }

    trienode(char c)
    {
        this->c = c;
        this->isword = false;
    }
};

class WordDictionary {
public:
    trienode* root;

    WordDictionary()
    {
        root = new trienode();
    }

    // Adds a word into the data structure.
    void addWord(string word) {
        trienode* p = root;
        for(int i = 0; i<word.length(); i++)
        {
            char c = word[i];

            if(p->hash.find(c) != p->hash.end())
            {
                p = p->hash[c];
            }
            else
            {
                trienode* newnode = new trienode(c);
                p->hash[c] = newnode;
                p = newnode;
            }

            if(i == word.length()-1)
            {
                p->isword = true;
            }
        }
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(string word) {
        return searchHelper(word, 0, root);
    }

    bool searchHelper(string word, int pos, trienode* cur)
    {
        if(cur == NULL)
        {
            return false;
        }

        if(pos == word.length())
        {
            return cur->isword;
        }

        char c = word[pos];

        if(c == '.')
        {
            for(auto& kv : cur->hash)
            {
                if(searchHelper(word, pos+1, kv.second))
                {
                    return true;
                }
            }
            return false;
        }

        if(cur->hash.find(c) == cur->hash.end())
        {
            return false;
        }

        return searchHelper(word, pos+1, cur->hash[c]);
    }
};

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");