Well this is an Age old question yet there seems to have a lots of room for
further modification..
1> Comparison of String Individually. Effective yet O(n2)
2> Why dont we let some function do the job say
if( Sort(String 1)==Sort(String 2))
Anagram;
All Work is Done by Sorting function. Use efficient Sort Say
qsort/heapsort and get the O value to O(nlogn) from O(n2) as we saw earlier
NOW IS that all we Computer Scientist do for this age old problem??
Naa.. here comes trie (Perhaps patricia trie sound better)
3> Bit Complex to implement/Hard to understand and use but highly efficient
.
Struct Trie {
char p;// Are we talking about String or Char?
Struct Trie *child[26];
bool End;
};
Yea this is the one for us. but As U can see each node holds 26
additional pointer overhead. Can some one try to rectify this structure ..
Well how abt this one
Struct Trie {
char letter;
bool end;
int startChildIndex;
int noof Child;
};
And that pushes all our refereces to array. So NO POINTERs.. here u guys
find how we can use the characteristic of array as pointer for efficency.
Anyway its coding time and as u all know wat to do next..
Please do your home work..
and have the most efficient Anagram Algo.. I guess its O(n) altogether..
but not only that it has the very small constant factor which means more
additional efficency..
HAPPY CODING
On Mon, May 14, 2012 at 8:06 PM, Piyush Khandelwal <
[email protected]> wrote:
> @ deepikaanand:
> I would like to paraphrase Gaurav's approach:
> what u have to do is take array a[26]={2,3,5,7,11............. first 26
> prime numbers }
>
> Now if ur words are EAT and ATE:
> for EAT..
> val1= a[ 'E' - 'A' ] * a [ 'A' - 'A' ] * a[ ' T '- 'A' ];
>
> for ATE:
> val2= a[ 'A' - 'A' ] * a [ 'T' - 'A' ] * a[ ' E '- 'A' ];
>
> Now if ( val1 == val 2) --> anagrams
> This will work in all the cases.................................
> Hope this will help u........... all the best
>
>
>
> On 13 May 2012 19:07, GAURAV CHAWLA <[email protected]> wrote:
>
>> @deepikaanand:
>>
>>
>> 1 is not a prime no. and also ignore 2 as chosen prime no,.
>>
>> On Sun, May 13, 2012 at 6:31 PM, deepikaanand <[email protected]>wrote:
>>
>>>
>>> @gaurav
>>> the approach suggested as : to have an array of 25 prime nos..How is
>>> it supposed to work ;
>>> cz(this is wat i have understood) if a :0 ,b:1,c:3,d:5,e:7
>>> then be = b + e = 1+7 =8
>>> and dc = d + c =5 +3 = 8..
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>
>>
>> --
>> Regards,
>> GAURAV CHAWLA
>> +919992635751
>> +919654127192
>>
>>
>>
>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> *Piyush Khandelwal**
> *Mobile No: 91-8447229204
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
