Pages

Friday, October 19, 2012

Nice Solution for detecting String anagrams (Algorithm)

Problem

Given two strings s1 and s2, we need to identify if s1 is an anagram of s2.
A string s1 is anagram of s2 if s1 is re-arrangement of the characters in s2.
e.g : s1="I am Lord Voldemort"
        s2="Tom Marvolo Riddle"
        are anagrams. 

Assumptions: 1. strings are made only of english characters and space.
                      2. space is ignored in the re arrangement (and in the original string)
                      3. case is ignored (lower and upper cases are same)

|s| denotes the length of string s.


Nice Solution: 

 Assign prime numbers to a to z characters. e.g- 3 for a, 5 for b, 7 for c etc.

Take product for prime numbers of string s1.
Take product for prime numbers of string s2.

Now, if the products are equal, the strings are anagrams.

Beauty of prime factorization. :-)

Algorithm will run in O( |s1| + |s2| ) 

Feel free to point out any flaws.

No comments:

Post a Comment