Performing a Trie with a Map
I was working on a solution to the problem today. But I'm stuck. I know how trie works, but the problem is I know how to implement it with static arrays and classes. Browsing the internet today I read that there is a way to implement the attempts using stl :: map. I tried today, but I still don't know how to insert elements into int. this structure.
Edit1: I'm trying to solve this problem: spoj.com/problems/TAP2012D I want to know how to add words to the trie using edit2: I know how the map works, I just don't know how the map trie works. I want someone to know about trying.
Here is what I have done so far
const int ALPH_SIZE = 26;
using namespace std;
struct trie{
map<char,int> M;
int x,y;
trie();
};
trie T[1000000];
trie::trie()
{
x=y=0;
}
int maximo;
void addtrie(string palabra)
{
int tam=palabra.size();
int pos=0;
for(int i=0;i<tam;i++)
{
if(T[pos].M.find(palabra[i])==T[pos].M.end())
{
T[pos].M[palabra[i]]=new trie();
T[pos].M[palabra[i]]=
}
}
}
source to share
A trie node stores a map of existing symbols and a flag indicating whether the node matches a word in the trie.
struct Node
{ map<char, Node*> a;
bool flag;
Node() { flag = false; }
};
Inserting is now similar to what you do with a static array, except that you are using a map here.
void insert(Node *x, string s)
{ for(int i = 0; i < s.size(); i++)
{ if(x->a.count(s[i]) == 0)
/* no outgoing edge with label = s[i] so make one */
{ x->a[ s[i] ] = new Node;
}
x = x->a[ s[i] ];
}
x->flag = true; /* new word */
}
source to share
Using unordered_map is better in my opinion.
struct TrieNode {
char c;
unordered_map<char, TrieNode*>links;
bool end;
};
TrieNode* insert(TrieNode* root, string word) {
TrieNode* current = root;
for (auto it: word) {
if (current->links.find(it) == current->links.end()) {
TrieNode* node = new TrieNode(); // possible memory leak?
node->c = it;
node->links = {};
node->end = false;
current->links[it] = node;
}
current = current->links[it];
}
current->end = true;
return root;
};
Of course, there can be a problem with memory leaks with TrieNodes that you create with the new operator. Perhaps something like tree traversal (based on DFS) to visit all nodes from the bottom up and remove them can help avoid memory leaks.
source to share