Tuesday, February 15, 2011

How to determine if two strings are anagrams?

First of all, what are anagrams? Well, anagrams are words that have the same characters which can be at different locations in the words. For example, "level" and "level" are anagrams, a special kind of anagrams because they are exactly the same in terms of characters and their locations in the words. Moreover, "rat" and "art" are also anagrams because all characters in "rat" are in "art", no more no less. Another example is "seek" and "ekes". Pay attention to the numbers of "e" letters in both words, they must be the same amount too. Thus, "seek" and "sek" are not anagrams.

Now we know what anagrams are. Let's take a look at the solution to the posted question:

#include<iostream>
#include<string>
using namespace std;

bool areAnagrams(string str1, string str2)
{
  if (str1.length() != str2.length())
  {
    return false;
  }

  int charsTracker[26] = {0};

  for (int i = 0; i < str1.length(); i++)
  {
    charsTracker[str1[i] - 'a']--;
    charsTracker[str2[i] - 'a']++;
  }

  for (int i = 0; i < 26; i++)
  {
    if (charsTracker[i] != 0)
      return false;
  }

  return true;
}

Explanation:

  1. First we check to see if the two strings have the same length. If not, they are not anagrams.
  2. Then, we declare an array of 26 integers. We will use this array to keep track of the characters in both strings. Why 26? You may ask. It is because we have 26 letters in the alphabet. Each of the letter is represented by an index in the array. And the value stored in each index represents the count of the letter's occurrence in both words.
  3. Next, we just loop through the strings and count the number of occurrences for each letter in both strings. For every letter in the first string, we'll subtract 1 from the count value stored in the index representing that letter. On the other hand, we'll add 1 for every letter in the second string. By doing this, we know that if both strings have the same letters, the final result will always be 0 because they cancel each other out through decrement and increment.
  4. Lastly, we check the array of counts. If any index has a non-zero value, then the strings are not anagrams

We'll do an example by checking for "rat" and "art". First run of the loop, "r" count is -1 because it is in first string and "a" count is 1 because it is in second string. Second run, "a" count is now 0 because it appears in the first string so 1 - 1 is 0. Moreover, "r" count is also 0 because it appears in the second string -1 + 1 = 0. Last run, "t" count is 0 because it appears in both strings 1 - 1 = 0. Thus, we know "rat" and "art" are anagrams because the resulting array contains all 0s

Thanks for reading.If you have any suggestion please leave it in the comment below.

4 comments:

  1. u r doin good job

    ReplyDelete
  2. #include
    #include
    using namespace std;

    bool areAnagrams(string str1, string str2)
    {
    if (str1.length() != str2.length())
    {
    return false;
    }

    int result =0;

    for (int i = 0; i < str1.length(); i++)
    {
    result += (str1[i] - 'a') - (str2[i] - 'a');
    }
    if(result == 0) return true;
    else return false;
    }

    ReplyDelete
  3. Rambabu, your solution is wrong! consider for example cat and cbs they are not anagrams but your functions returns true!!

    ReplyDelete
  4. i could't understand the logic of this piece of code(charsTracker[str1[i] - 'a']--;
    charsTracker[str2[i] - 'a']++;) could you please explain it..

    ReplyDelete