Tuesday, August 4, 2015

LeetCode OJ - Implement Trie (Prefix Tree)

Problem:

Please find the problem here.

Solution:

This is basically the same as the Trie (not even the compressed one) in my previous post here.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/implement-trie-prefix-tree/

#include "LEET_IMPLEMENT_TRIE_PREFIX_TREE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_IMPLEMENT_TRIE_PREFIX_TREE
{
    class TrieNode
    {
    public:
        map<char, TrieNode*> children;

        // Initialize your data structure here.
        TrieNode()
        {

        }

        ~TrieNode()
        {
            for (map<char, TrieNode*>::iterator ci = this->children.begin(); ci != this->children.end(); ci++)
            {
                delete ci->second;
            }
        }
    };

    class Trie {
    private:
        TrieNode* root;

        TrieNode* run(string word, bool create)
        {
            TrieNode* current = this->root;
            for (unsigned int i = 0; i < word.size(); i++)
            {
                map<char, TrieNode*>::iterator probe = current->children.find(word[i]);
                if (probe == current->children.end())
                {
                    if (create)
                    {
                        TrieNode* newNode = new TrieNode();
                        current->children.insert(pair<char, TrieNode*>(word[i], newNode));
                        current = newNode;
                    }
                    else
                    {
                        return NULL;
                    }
                }
                else
                {
                    current = probe->second;
                }
            }

            return current;
        }
    public:
        Trie()
        {
            this->root = new TrieNode();
        }

        // Inserts a word into the trie.
        void insert(string word)
        {
            this->run(word + '\0', true);
        }

        // Returns if the word is in the trie.
        bool search(string word)
        {
            TrieNode* current = this->run(word + '\0', false);
            return current != NULL && current->children.size() == 0;
        }

        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix)
        {
            TrieNode* current = this->run(prefix, false);
            return current != NULL;
        }
    };
};

using namespace _LEET_IMPLEMENT_TRIE_PREFIX_TREE;

int LEET_IMPLEMENT_TRIE_PREFIX_TREE()
{
    Trie trie;
    trie.insert("some");
    trie.insert("something");
    cout << trie.startsWith("ksom") << endl;
    return 0;
}

No comments :

Post a Comment