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;
}
1 Answer 1
#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.