4

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";

for (int i = 1; i < 6; i++) {
   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";
}
Community
  • 1
  • 1
Ajai
  • 3,440
  • 5
  • 28
  • 41
  • 4
    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

4 Answers4

6

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.

Valmond
  • 2,897
  • 8
  • 29
  • 49
  • 1
    ["Necessary but not sufficient"](http://en.wikipedia.org/wiki/Necessary_and_sufficient_condition) – MSalters Oct 21 '11 at 11:59
1

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.

JoeG
  • 12,994
  • 1
  • 38
  • 63
0

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.

Stefan
  • 3,669
  • 2
  • 32
  • 43
-1

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;
else
    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;
else
    std::cout << "s1 and s3 aren't anagram" << std::endl;
Tio Pepe
  • 3,071
  • 1
  • 17
  • 22