Implementation of Trie data structure accommodating varying number of children

Question

I've used the Trie data structure to solve the following problem:

Given an array of words, print all anagrams together. For example, if the given array is {"cat", "dog", "tac", "god", "act"}, then output may be "cat tac act dog god".

The following is my C++ implementation which can accommodate varying number of children.

#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <algorithm>
using namespace std;

struct Trie_node_base
{
    vector<Trie_node_base*> child;
    int num_of_child;

    Trie_node_base(int n)
    {
        num_of_child = n;
        for(int i = 0; i < n; ++i)
            child.push_back(NULL);
    }   
};

struct Trie_node : public Trie_node_base
{
    bool is_word;
    vector<vector<string>::const_iterator> head;

    Trie_node(int num):Trie_node_base(num), is_word(false){} 
};

class Trie
{
public:
    Trie(int n=26)
    {
        root = new Trie_node(n);
    }
    ~Trie()
    {
        destroy(root);
    }

    void insert_trie_node(const string& w, vector<string>::const_iterator ind);
    Trie_node* get_root_node()
    {
        return root;
    }

private:
    Trie_node* root;
    void destroy(Trie_node* root);
};

void Trie::insert_trie_node(const string& w, vector<string>::const_iterator ind)
{
    Trie_node* r = root;

    string::const_iterator runner = w.begin();
    for(; runner!=w.end(); ++runner)
    {
        char cur_char = *runner;
        int i = cur_char - 'a';

        if(r->child[i] == NULL)
        {
            r->child[i] = new Trie_node(r->num_of_child);
        }
        r = (Trie_node*)r->child[i];            
    }

    if(!r->is_word)
        r->is_word = true;
    r->head.push_back(ind);
}

void Trie::destroy(Trie_node* root)
{
    vector<Trie_node_base*>::iterator it = (root->child).begin();

    for(; it != (root->child).end(); ++it)
    {
        if(*it != NULL)
            destroy((Trie_node*)(*it));
    }

    delete root;
}


void traversal_trie(const vector<string>& word_arr, Trie_node* r)
{
    size_t i;

    if(r->is_word)
    {        
        vector<vector<string>::const_iterator>::iterator it = (r->head).begin();
        for(; it != (r->head).end(); ++it)
        {
            cout << *(*it) << endl;
        }        
    }


    for(i = 0; i < r->num_of_child; ++i)
    {
        if(r->child[i] != NULL)
            traversal_trie(word_arr, (Trie_node*)r->child[i]);
    }    
}

void cluster_anagrams(const vector<string>& word_arr, size_t size)
{
    Trie* trie = new Trie(26);

    vector<string>::const_iterator it = word_arr.begin();       
    for(; it != word_arr.end(); ++it)
    {
        string cur_str = *it;
        sort(cur_str.begin(), cur_str.end());
        trie->insert_trie_node(cur_str, it);        
    }     
    traversal_trie(word_arr, trie->get_root_node());
}

int main()
{
    const char* word_arr[] = {"cat", "dog", "tac", "god", "act", "gdo"};
    size_t size = sizeof(word_arr) / sizeof(word_arr[0]);    
    vector<string> word_arr1(word_arr, word_arr+size);


    cluster_anagrams(word_arr1, size);    

    system("pause");
    return 0;
}

Answer 1

Your code does several things more complex than required. In no particular order:

• What purpose does Trie_node_base serve? You don’t need a base class here since you only inherit from it once.
• Worse, your base class doesn’t have a virtual destructor.

• To create an array of size n, you use a loop and push_back. Much easier would be to use the proper initialiser:

  Trie_node_base(int n) :
      num_of_child(n) ,
      child(n)
      { }
  

• In fact, you generally fail to use initialisers, and instead re-assign values inside the constructor.

• Consider proper naming. In the above code snippet, it should really be number_of_children and children (plural!).
• The num_of_child member is redundant – the same information is stored in the vector.
• The tree node root doesn’t need to, and shouldn’t be, a pointer.
• In general, your use of pointers and manual memory management makes the code vastly more complex and brittle (and requires the existence of the destroy method). If you need to use pointers, use smart pointers (std::unique_ptr in this case).

• Better yet, omit pointers entirely. They are utterly unnecessary here. Unfortunately though, you cannot use std::vector with an incomplete class (the standard screwed up here). But you can (and should!) use boost::container::vector. Thus your tree node implementation becomes:

  struct Trie_node
  {
      boost::container::vector<Trie_node> children;
      bool is_word;
  
      Trie_node(int n)
          : children(n)
          , is_word(false)
      { }
  };
  

… There’s more but these are the essential points that will help reduce code complexity.

Answer 2

It seems you used wrong data structure for the task. All what you need is a simple dictionary (the c++ map class). The idea to find all anagrams for a specific word is the following:

step 1: building map structure based on the dictionary - the key is a sorted by symbols word, the value is the list of anagrams.

Example.

dictionary : tac god act

the map structure will be:

act: [tac, act] dgo: [god]

step 2: search - we take the checked words one by one, sort their chars and use the result string as a key.

checked words: cat dog

cat -> act (letters are sorted) -> get anagrams from the dictionary for the key act -> [tac, act] dog -> dgo (lettes are sorted) -> get ananagrams from the dictionary for the key dgo -> [god]

Here is the complete python solution for the similar puzzle (it could be like a pseudocode for the solution), the first parameter is a dictionary file, the second is the list of the checked words:

import sys
checkwords = open(sys.argv[2]).read().split()
lens = set(len(word) for word in checkwords)
index = {}
for word in open(sys.argv[1]).read().split(): 
   if len(word) in lens:
    index.setdefault(''.join(sorted(word)), []).append(word)
for word in checkwords: 
   anagrams = index[''.join(sorted(word))]
   print str(len(anagrams)) + '\n' + '\n'.join(anagrams)