Take the 2-minute tour ×

I am sure this question has been discussed in the distant past several times on Stack Overflow. I am just trying to verify whether my answer is valid or not. I saw this question in this thread. I am sorry that this post is a duplicate of the thread and if it has to be removed, I shall do it.

I thought of doing this in a much more simple way. By just XORing the characters in the string.

So O(n) for XORing each character and O(1) for comparison of last characters in both the strings which gives a O(n) solution.

Even though the last characters may be any special symbol but if the strings are anagrams they still end up being the same. Am I right in this logic?

So instead of doing all sorting and hashing can this solution be adopted? My code goes like this:

char a[7] = "Length";
char b[7] = "enghtL";

   a[i] = a[i] ^ a[i-1];
   b[i] = b[i] ^ b[i-1];

if (a[5] == b[5]) {
   cout << "\n The strings are anagrams";
else {
   cout << "\n No they are not";
share|improve this question
According to your program, "ab" is an anagram of "ef". I'm afraid this approach can't possibly work. –  TonyK Oct 21 '11 at 11:11
So, basically, "is ((a XOR b XOR c) ≡ (c XOR a XOR b) ≡ (b XOR c XOR a) ≡ (c XOR b XOR a)) ∧ ((a XOR b) ≠ (a XOR d))a, b, c, d, and for generalisations in arity?" I think not. –  Lightness Races in Orbit Oct 21 '11 at 11:11
@TonyK: Wow! +1. Didn't think about it. –  Ajai Oct 21 '11 at 11:44
When I've needed to find anagrams, I've just sorted the letters in the words and checked if the result is the same. –  visitor Oct 21 '11 at 11:50
add comment

5 Answers

up vote 5 down vote accepted

I'm sorry but this won't work.

Sure, if it is an anagram, the code (if it works correctly) will say so but you will also have a lot of 'false positives' because several (different) strings can yield the same output.

share|improve this answer
+1: e.g. "ab" and "ef" as TonyK points out. –  Lightness Races in Orbit Oct 21 '11 at 11:17
"Necessary but not sufficient" –  MSalters Oct 21 '11 at 11:59
add comment

You're condensing all the information about an n-byte string into a single byte - effectively a very basic hash. Whenever you get a hash collision between two strings that aren't anagrams you'll return a false positive.

If you want an O(n) method for finding anagrams, sort the words using a counting sort then compare the results for equality.

share|improve this answer
add comment

This code might be useful as part of a solution.

My approach would be:

Check if the two words have the same amount of letters, if not then it cannot be an anagram. Then sort the letters or each word into alphabetical (or any other) order Step through the word lists and return false if the letters are not equal.

share|improve this answer
add comment

Xor each character of the first string with each character of the second string. The result should be 0 in casse of the string being anagrams.

share|improve this answer
add comment

In C++ you can use string reverse iterators:

std::string s1 = "Length";
std::string s2 = "htgneL";
std::string s3 = "htgnel";

if (s1 == std::string(s2.rbegin(), s2.rend()))
    std::cout << "s1 and s2 are anagram" << std::endl;
    std::cout << "s1 and s2 aren't anagram" << std::endl;

if (s1 == std::string(s3.rbegin(), s3.rend()))
    std::cout << "s1 and s3 are anagram" << std::endl;
    std::cout << "s1 and s3 aren't anagram" << std::endl;
share|improve this answer
That only works for reversed strings, which is just one out of loads of possible anagrams. –  Lightness Races in Orbit Oct 21 '11 at 11:29
@TomalakGeret'kal you are right, of course, I get confused about anagram definition. –  Tio Pepe Oct 21 '11 at 11:32
Anagram != palindrome –  Paul R Oct 21 '11 at 15:16
add comment

Your Answer


