Find number of anagram groups ?

Question

eg: array = "amber","gaura","sahil","mabre","rauag","halis", "bamre"}
then no. of anagram groups = 3.
"amber" ,"mabre" ,"bamre" form one group.

Comments

shall I assume all the char array have same length and same case? [lower / upper case]

Answer 1

OP1 : First sort each string lexicographically

if Given array is
array = {"amber","gaura","sahil","mabre","rauag","halis", "bamre"}
after above operation it will become
array = {"abemr","aagru","ahils","abemr","aagru","ahils", "abemr"}

OP2 : then sort the array
after above operation it will become
array = {"aagru","aagru","abemr","abemr","abemr","ahils","ahils"}

OP3 : Now the common strings are in sorted order so.. we can find number of groups easily in one single scan..

Order : Number of strings in array = n and length of each string is at max m then
OP1 : O(m)
OP2 : O(mnlogn)
OP3 : O(n)
Total : O(mnlogn)

Comments

Thanks Good one.
Can you please tell the complexity.