C++ solution using stl container


  • 0
    K

    Basically it's a trie structure, but here we use std::map to contain all trie nodes.
    One good thing to use this structure is, you don't need to worry about the memory leakage during destruction.

    class WordDictionary {
    public:
    
    struct Node
    {
        bool here;
        map<char,Node> next;
    };
    
        Node root;
    
        void addWord(string word)
        {
            auto* cur = &root;
    		map<char,Node>::iterator iter;
            for (int i = 0 ; i < word.size(); ++i)
            {
                iter = cur->next.find(word[i]);
                if (iter == cur->next.end())
                {
    				iter = cur->next.insert(make_pair(word[i],Node())).first;
    				iter->second.here = false;
                }
                cur = &iter->second;
            }
            cur->here = true;
        }
    
        bool search(string word)
        {
            return search(word,0,root);
        }
        
        
        bool search(string& word, int cur, Node& curNode)
        {
            if (cur == word.size())
                return curNode.here;
            
            if (word[cur] == '.')
            {
                for (auto iter = curNode.next.begin(); iter != curNode.next.end(); ++iter)
                {
                    if (search(word, cur+1 , iter->second))
                        return true;
                }
                return false;
            }
            else
            {
                auto iter = curNode.next.find(word[cur]);
                if (iter == curNode.next.end())
                    return false;
                return search(word, cur+1 , iter->second);
            }
            
            return false;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.