1
\$\begingroup\$

I've made a short program to determine if a string is permutation of another string.

Example input/output :

a) 123, 112 <- False

b) 123, 321 <- True

c) 112, 121 <- these don't count as permutations since they have duplicate characters

    private static void Main()
    {
        string a = Console.ReadLine();
        string b = Console.ReadLine();                    
        Console.WriteLine(IsPermutation(a, b));
        Console.ReadKey();
    }

    private static bool IsPermutation(string first, string second)
    {
        if (first.Length != second.Length)
        {
            return false;
        }
        for (int i = 0; i < first.Length; i++)
        {
            if (first.Count(t => t == second[i]) != second.Count(t => t == first[i]))
            {
                return false;
            }
        }
        return true;
    }

I wonder if it can be optimized.

\$\endgroup\$
2
  • \$\begingroup\$ It is unclear what you mean by "permutation of another string". Please add a thorough explanation, as well as examples to illustrate what is or isn't a "permutation". \$\endgroup\$ Dec 8 '16 at 0:09
  • \$\begingroup\$ I've updated the question. \$\endgroup\$
    – Denis
    Dec 8 '16 at 0:15
0
\$\begingroup\$

This can almost certainly be optimized. Look at your algorithm:

  1. Take the next character from the first string
  2. Count all instances of that character in the both strings by iterating over them.
  3. Compare the count of the character in each string.

Now, let's look at how many times you iterate the strings: The first string is iterated N * N times, and the second string is iterated N * N times, where N is the count of the characters in the string. This makes 2N^2 iterations. It would probably be much faster (depending on the string length) to split these strings into character arrays, sort each of the arrays, and do an iteration like this:

list1 = Array.Sort(first.ToCharArray());
list2 = Array.Sort(second.ToCharArray());

for (var i = 0; i < list1.Count; i++)
{
    if (list1[i] != list2[i])
    {
        return false;
    }
}

return true;

Update:

I misunderstood what your program was meant to do the first time around.

First, you should understand that a permutation is:

Permutation: A way, especially one of several possible variations, in which a set or number of things can be ordered or arranged.

At first, I didn't understand that duplicate items within the string were not allowed.

Second, your program does not work correctly. Consider the following strings: "13234" and "43231". Your program will return true for these values because the "3"s are in the same indexes in the string, and therefore the count for each item at the index matches. "123344" and "124433" also return true because you only check that the items in the same index in each string have the same count.

To correctly handle this with your method, you would need to first compare the strings and return true for duplicate values (e.g. "1233" is considered a "permutation" of "1233"). Then, you would need to check that the count of each item in the string is 1 and that each item is in the other string.

If I were to implement this program, I would do it as Paparazzi suggested, except I would check that each item is not already in the dictionary as I do the first iteration to prevent duplicates in the first string and ensure that the value is 1 every time I try to remove an item to prevent duplicates in the second string.

If you were sure that each string as no duplicates, you could use Dmitry's method, but you clearly do not expect each string to contain no duplicates because you attempted to rule out duplicates in your first solution.

\$\endgroup\$
9
  • \$\begingroup\$ That's not correct just try 123 and 321 as input \$\endgroup\$
    – Denis
    Dec 7 '16 at 22:07
  • \$\begingroup\$ I edited it to show the sorting part, instead of just the comparison part. Is it clearer now? \$\endgroup\$
    – user34073
    Dec 7 '16 at 22:13
  • \$\begingroup\$ And yes, my solution will work for inputs of "123" and "321". \$\endgroup\$
    – user34073
    Dec 7 '16 at 22:14
  • \$\begingroup\$ Yes you've made it clearer now it works just fine \$\endgroup\$
    – Denis
    Dec 7 '16 at 22:20
  • \$\begingroup\$ Sort is on average is an O(n log n) operation, where n is Count; in the worst case it is an O(n ^ 2) operation. \$\endgroup\$
    – paparazzo
    Dec 7 '16 at 23:15
2
\$\begingroup\$

You could use the SetEqual<T> helper method from this answer.
It uses a dictionary as follows:

  1. The dictionary is filled with the items of the first collection and with their number of occurences.
  2. Number of occurences is decreased for each item in the second collection.

Thus your method can be rewritten as:

private static bool IsPermutation(string first, string second)
{
    if (first.Length != second.Length)
    {
        return false;
    }
    return SetEqual(first, second);
}

If you are sure that strings contain only unique chars, there is a more efficient approach using the HashSet<T>:

private static bool IsPermutation(string first, string second)
{
    if (first.Length != second.Length)
    {
        return false;
    }
    HashSet<char> chars = new HashSet<char>(first);
    return second.All(chars.Contains);
}
\$\endgroup\$
9
  • \$\begingroup\$ Those are variations not permutations. \$\endgroup\$
    – Denis
    Dec 7 '16 at 22:41
  • \$\begingroup\$ @denis My English isn't good enough so please point me to the difference. \$\endgroup\$
    – Dmitry
    Dec 7 '16 at 22:44
  • \$\begingroup\$ the permutations of 123 are (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1) while the variations are all of the above but they include (1,1,1), (1,1,2), and so on.. the difference is that permutations don't have repetitive characters. \$\endgroup\$
    – Denis
    Dec 7 '16 at 22:49
  • \$\begingroup\$ @denis Do you mean we cannot say that (1,2,1) is a permutation of (1,1,2)? \$\endgroup\$
    – Dmitry
    Dec 7 '16 at 22:56
  • 1
    \$\begingroup\$ @denis it's not quite clear whether you're permuting tuples (which allow duplicates) or sets (which don't do so) ... could you clarify a bit? because strings in general are basically tuples. \$\endgroup\$
    – Vogel612
    Dec 7 '16 at 23:04
0
\$\begingroup\$

I think this is going to be O(n) as Dictionary Add and Lookup are O(1)

private static bool IsPermutation(string first, string second)
{
    if (first.Length != second.Length)
        return false;
    if (first.Length == 0)
        return false;
    Dictionary<char, int> countEm = new Dictionary<char, int>(first.Length);
    foreach (char c in first)
    {
        if (countEm.Keys.Contains(c))
            countEm[c]++;
        else
            countEm.Add(c, 1);
    }
    foreach (char c in second)
    {
        if (countEm.Keys.Contains(c))
        {
            if (countEm[c] == 0)
                return false;
            countEm[c]--;
        }
        else
            return false;
    }
    return true;
}
\$\endgroup\$
10
  • \$\begingroup\$ Isn't this the same approach as in my answer? \$\endgroup\$
    – Dmitry
    Dec 7 '16 at 23:25
  • \$\begingroup\$ It is similar but I think it is more efficient. I did not look to your link before writing this. \$\endgroup\$
    – paparazzo
    Dec 7 '16 at 23:38
  • 1
    \$\begingroup\$ @denis I think you were a little quick to accept an answer. \$\endgroup\$
    – paparazzo
    Dec 7 '16 at 23:40
  • \$\begingroup\$ @denis Uh, even the accepted answer said this is probably faster. \$\endgroup\$
    – paparazzo
    Dec 8 '16 at 0:07
  • 1
    \$\begingroup\$ People often forget the notion of big O notation. The dictionary contains is indeed O(1) but that does not mean that this algorithm will be faster everytime comparing to the sorting approach. Using an auxiliary lookup will occur to a significant overhead, that's why the sorted algorithm might be faster on some scenarios. The size of first needs to be very big to see the gain with this approach. It would be interesting to see an array in action instead of a dictionary. After all there are only 26 English letters (52, if you are case sensitive). That dismisses other letters though. \$\endgroup\$ Dec 8 '16 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.