There's another clever solution using prime numbers which is O(n): You create a map of characters to prime numbers (just use the first 26 primes for simplicity), then store a "total" value and for each character in the string, multiply the total by the prime value of the character to get the "prime sum". Then check if the prime sum of the two words is equal.

This is a great solution Sam, the only thing I worry about is that multiplication though theoretically is an O(1) operation, but in for strings of size > 50, we will have resort to Big integers and multiplication there is not exactly O(1).

Also played a bit of code golf with your algorithm

A valid point - I didn't consider large strings that might cause an overflow. At that point a character map solution may become more efficient than using big arithmetic, though it would be interesting to test and see.

## re: Learning Algorithms with JS, Python and Java 7: Anagrams VIEW POST

TOP OF THREAD FULL DISCUSSIONThere's another clever solution using prime numbers which is O(n): You create a map of characters to prime numbers (just use the first 26 primes for simplicity), then store a "total" value and for each character in the string, multiply the total by the prime value of the character to get the "prime sum". Then check if the prime sum of the two words is equal.

Edit: Snippet to make the method clearer

This is a great solution Sam, the only thing I worry about is that multiplication though theoretically is an O(1) operation, but in for strings of size > 50, we will have resort to Big integers and multiplication there is not exactly O(1).

Also played a bit of code golf with your algorithm

A valid point - I didn't consider large strings that might cause an overflow. At that point a character map solution may become more efficient than using big arithmetic, though it would be interesting to test and see.

Nice golfed solution!

Nice thing about this method, you can use modulus to check if a string is a substring of another (“apple” to “applesauce”).

That might give false positive for jumbled words, for example paple would pass the modulous check.