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.

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++ code. I use raw pointer to implement varying number of children for practice. Actually, I guess maybe it's better to adopt STL containers.

#include <iostream>
#include <cstring>
using namespace std;

struct Index_node_base
{
    Index_node_base* next;
    Index_node_base():next(NULL){}  
};

struct Index_node : public Index_node_base
{
    int index;
    Index_node(int i):index(i), Index_node_base(){}
};

void insert_index_node(Index_node** head, int i)
{
    Index_node* node = new Index_node(i);
    node->next = (*head);
    *head = node;
}

struct Trie_node_base
{
    typedef Trie_node_base* Base_ptr;

    Base_ptr* child;
    int num_of_child;

    Trie_node_base(int n)
    {
        child = new Base_ptr[n];
        for(int i=0; i < n; ++i)
            child[i] = NULL;
        num_of_child = n;
    }

    ~Trie_node_base()
    {
        delete [] child;
    }
};

struct Trie_node : public Trie_node_base
{
    bool is_end;
    Index_node* head;
    Trie_node(int n):Trie_node_base(n), is_end(false), head(NULL){}
};

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

    void insert_trie_node(const char* w, int ind);
    Trie_node* get_root_node();

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

Trie_node* Trie::get_root_node()
{
    return root;
}

void Trie::insert_trie_node(const char* w, int ind)
{
    Trie_node* r = root;
    while(*w)
    {
        int i = *w - 'a';
        if(r->child[i] == NULL)
        {
            r->child[i] = new Trie_node(r->num_of_child);
        }
        r = (Trie_node*)r->child[i];
        ++w;
    }

    if(r->is_end)
    {
        insert_index_node(&(r->head), ind);
    }
    else
    {
        r->is_end = true;
        r->head = new Index_node(ind);
    }
}

void traversal_trie(const char* word_arr[], Trie_node* r)
{
    size_t i;

    if(r->is_end)
    {        
        Index_node* h = r->head;
        while(h != NULL)
        {
            printf("%s\n", word_arr[h->index]);
            h = (Index_node*)h->next;
        }
    }


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

void Trie::destroy(Trie_node* root)
{
    size_t i;

    for(i = 0; i < root->num_of_child; ++i)
    {
        if(root->child[i] != NULL)
            destroy((Trie_node*)root->child[i]);
    }

    if(root->is_end)
    {
        Index_node* h = root->head;
        Index_node* tmp = NULL;

        while(h != NULL)
        {
            tmp = (Index_node*)h->next;
            delete h;
            h = tmp;
        }        
    }

    delete root;
}

static int comp_char(const void* x, const void* y)
{
    const char* c1 = (const char*)x;
    const char* c2 = (const char*)y;

    return *(c1) - *(c2);
}

static void cluster_anagrams(const char* word_arr[], size_t size)
{
    Trie* trie = new Trie(26);
    size_t i;
    char* buffer;

    for(i = 0; i < size; ++i)
    {
        int len = strlen(word_arr[i]);
        buffer = new char [len+1];
        memcpy(buffer, word_arr[i], len+1);        
        qsort(buffer, strlen(buffer), 1, comp_char);   
        trie->insert_trie_node(buffer, i);          
        delete buffer;
    }

    cout << "Debug!" << endl;
    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]);
    cluster_anagrams(word_arr, size);    

    system("pause");
    return 0;
}
share|improve this question

1 Answer 1

up vote 1 down vote accepted
#include <cstring>

Avoid including C headers when programming C++.

struct Index_node_base
{
    Index_node_base* next;
    Index_node_base():next(NULL){}  
};

struct Index_node : public Index_node_base
{
    int index;
    Index_node(int i):index(i), Index_node_base(){}
};

void insert_index_node(Index_node** head, int i)
{
     Index_node* node = new Index_node(i);
     node->next = (*head);
     *head = node;
}

This is overkill as you are just re-implementing a list of numbers / characters.

const char*

This is C code, consider using the C++ std::string instead.

const char* word_arr[]

For example, this one should be a std::list<std::string> (a.k.a. list<string>)

 printf("%s\n", word_arr[h->index]);

Again C, use the C++ iostreams instead. This should be like cout << ... << endl;

while(*w)
{
    int i = *w - 'a';
    if(r->child[i] == NULL)
    {
        r->child[i] = new Trie_node(r->num_of_child);
    }
    r = (Trie_node*)r->child[i];
    ++w;
}

You can use iterators and STL algorithms to do this in one line.

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

This would also be one line using for_each on iterators and passing traversal_trie.

void Trie::destroy(Trie_node* root)

You won't need destory anymore as a result; also, there's a chance you might not need pointers.

static int comp_char(const void* x, const void* y)
{
    const char* c1 = (const char*)x;
    const char* c2 = (const char*)y;

    return *(c1) - *(c2);
}

This is messsy, you are doing useless C style voids and casts and not using C++ overloading. This body would have been something along the line of just the line return c1 < c2;

for(i = 0; i < size; ++i)
{
    int len = strlen(word_arr[i]);
    buffer = new char [len+1];
    memcpy(buffer, word_arr[i], len+1);        
    qsort(buffer, strlen(buffer), 1, comp_char);   
    trie->insert_trie_node(buffer, i);          
    delete buffer;
}

memcpy? Not necessary, std::string allows you to copy the string and not mess with memory.

share|improve this answer

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.