Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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;
}
share|improve this question

2 Answers 2

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.

share|improve this answer
    
Some of my suggestions from codereview.stackexchange.com/questions/18776/… are still missing in his revision, like the use of for_each and similar algorithms; I suppose he could take a look at those if he's done with yours and still wants to improve it further. Seems I missed a few as well reading your suggestions... :) –  Tom Wijsman Nov 19 '12 at 12:32
    
@Tom Oops, I hadn’t noticed the previous thread at all. Good job there. –  Konrad Rudolph Nov 19 '12 at 12:46

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)
share|improve this answer
    
I don’t think the trie is the wrong data structure here. In fact, a trie is a lookup structure for string keys, and potentially more efficient than other general-purpose dictionaries. –  Konrad Rudolph Nov 29 '12 at 21:38
    
1. Dictionaries are built-in and high optimized classes that exist in every modern language. If you want to port code to python or ruby or java - you need to rewrite the Trie class. 2. Trie class is not memory efficient class - try to put the big dictionary into the trie. –  cat_baxter Nov 30 '12 at 9:50
    
So what? I’m assuming that the question was asked in a CS course in the context of tries. And in fact tries are a very common data structure because they are indispensable in many fields, and implementations exist for all relevant programming languages. –  Konrad Rudolph Nov 30 '12 at 9:52
    
That trie structure doesn't support unicode strings - so it's just a show stopper for a real use and a good chance to fail the interview. –  cat_baxter Nov 30 '12 at 10:12
    
Superficial knowledge can be a dangerous thing so maybe you should just accept that I know what I’m talking about. Like I said, the trie in OP’s question is probably from the context of a CS course where this is irrelevant (forget Unicode! It only accepts lower-case letters). Likewise in interviews: just be able to explain the limitations. If that’s a show-stopper then the interviewer is an idiot. In general, a trie can be written with Unicode in mind but a restricted alphabet implementation is often sufficient / superior because of the special use-cases it’s employed to solve. –  Konrad Rudolph Nov 30 '12 at 10:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.