Algorithms: Determine if Two Strings Are Permutations of Each Other

In McDowell's (2012) set of problems, we come across problem 1.3: Given two strings, write a method to decide if one is a permutation of the other. If two strings are permutations, then they will have the same characters. Given "ABCDEF" and "FEDCBA", we can determine that these strings are permutations. They contain the same characters, just in different orders.

To go about solving this problem, I decided to use a similar approach to previous string algorithm problems and use an array to produce behavior that is similar to a hash table. An array is declared with spots equal to the number of possible characters. In extended ASCII, this is 256. My array has indices from 0 to 255.

There are two basic checks that I came up with to determine if the strings are permutations. The first is to check the length. If the strings are not the same length, they cannot be permutations. Next, I simply count the characters in each string. If the counts do not match, the strings are not permutations.

I did the counts by first adding the counts from the first string to the count array, and then subtracting the counts from the second string from the count array. At this point, each index in the count array should be 0. If any spot does not equal 0, then the strings are not permutations.

Here is the complete source code. I've written this one in C# in order to brush up on the basic syntax instead of C++.

//Author: Brandon Theolet
//
//McDowell, G. L. (2012). Cracking the coding interview: 150 programming questions and solutions (5th ed.). Palo Alto, CA: Career Cup, LLC.
//Problem 1-3: Given two strings, write a method to decide if one is a permutation of the other.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Problem1_3
{
    class Problem1_3
    {
        static void Main(string[] args)
        {
            //Testing harness. Prompts the user for two strings
            //and invokes the method that compares for permuatations.

            string myString1, myString2;

            Console.Clear();
            Console.Out.Write("Please enter any string: ");
            myString1 = Console.In.ReadLine();

            Console.Out.Write("Please enter another string: ");
            myString2 = Console.In.ReadLine();

            if (isPermutation(myString1, myString2)) Console.Out.WriteLine("These strings are permutations.\n");
            else Console.Out.WriteLine("These strings are not permutations.\n");

            Console.Out.Write("Please press enter to continue...");
            Console.In.ReadLine();
        }

        static private bool isPermutation(string myString1, string myString2)
        {
            //If the strings are different lengths, they are not
            //permutations.
            if (myString1.Length != myString2.Length) return false;

            //Create an array to count the number of each specific
            //character in the strings.
            int[] characterCount = new int[256];
            int charIndex;

            //Populate the array with default value 0.
            for (int index = 0; index < 256; index++)
            {
                characterCount[index] = 0;
            }

            //Count the number of each character in the first
            //string. Add the count to the array.
            foreach (char myChar in myString1.ToCharArray())
            {
                charIndex = (int)myChar;
                characterCount[charIndex]++;
            }

            //Count the number of each character in the second
            //string. Subtract the count from the array.
            foreach (char myChar in myString2.ToCharArray())
            {
                charIndex = (int)myChar;
                characterCount[charIndex]--;
            }

            //If the strings are permutations, then each character
            //would be added to our character count array and then
            //subtracted. If all values in this array are not 0
            //then the strings are not permutations of each other.
            for (int index = 0; index < 256; index++)
            {
                if (characterCount[index] != 0) return false;
            }

            //The strings are permutations of each other.
            return true;
        }
    }
}


Reference:

McDowell, G. L. (2012). Cracking the coding interview: 150 programming questions and solutions (5th ed.). Palo Alto, CA: Career Cup, LLC.