Given two strings, is one an anagram of the other

Question

I just started going through "Cracking the Coding Interview" and have the following solution for this problem:

public static bool isAnagram(String s, String t)
{
    if (s == "" || t == "") return false;
    else if (s.Length != t.Length) return false;

    int[] letters = new int[256];
    char[] s_array = s.ToCharArray();

    foreach(char c in s_array) 
    { 
        letters[c]++;  
    }

    for (int i = 0; i < t.Length; i++)
    {
        int c = t[i];
        if (--letters[c] < 0) 
        {
            return false;
        }
    }
    return true;
}

This is pretty much the verbatim solution from the book, only in C#, not Java, and with some additional nullchecks. I also solved the question using LINQ but wanted an additional solution that didn't involve sorting.

Can this approach be made a bit more elegant? The code works just fine, I just want to know if there is a more elegant or better solution out there. Thanks!!

`char` represents a unicode character in [UTF-16](http://msdn.microsoft.com/en-gb/library/system.char.aspx). There are more then 256 of them (and even if there weren't, there are surrogates to consider) — Damien_The_Unbeliever, Apr 22 '13 at 07:34
What do you mean by 'more elegant'? This is pretty elegant in my book. — Emond, Apr 22 '13 at 07:36
I think sorting and char-counting are the only 2 viable solutions to this problem, and of the second this is a pretty sweet implementation. So yeah, no idea what kind of more 'elegant' solution you're looking for. — Niels Keurentjes, Apr 22 '13 at 07:41
And char-counting is essentially a bucket sort in disguise. There is no solution without sorting ;-) — DasKrümelmonster, Apr 22 '13 at 07:46

Denys Denysenko · Accepted Answer · 2014-08-21T08:24:26.003

16

This code should work for you:

public static bool IsAnagram(string s1, string s2)
{
    if (string.IsNullOrEmpty(s1) || string.IsNullOrEmpty(s2))
        return false;
    if (s1.Length != s2.Length)
        return false;

    foreach (char c in s2)
    {
        int ix = s1.IndexOf(c);
        if (ix >= 0)
            s1 = s1.Remove(ix, 1);
        else
            return false;
    }

    return string.IsNullOrEmpty(s1);
}

Edit: Added non linq version.

You also may add some additional checks for null and empty values and move solution to StringBuilder to improve performance but intent of code is clear.

edited Aug 21 '14 at 08:24

answered Apr 22 '13 at 07:47

Denys Denysenko

7,598
1
20
30

From OP: "I also solved the question using LINQ but wanted an additional solution that didn't involve sorting." – rliu Apr 22 '13 at 07:50
That's just gorgeous :), thank you – mynameisneo Apr 22 '13 at 08:14
@mynameisneo, thank you for the kind words! – Denys Denysenko Apr 22 '13 at 08:21
1

You can little modify to increase performance if (ix >= 0) { s1 = s1.Remove(ix, 1); } else return false; – Umesh CHILAKA Apr 22 '13 at 08:28
isn't this a O(n2) solution ? – Rohit Aug 08 '14 at 10:33
Not sure why this a more elegant solution than sorting which can be done in either O(n) with Radix sort or O(nlogn) with merge-sort, both are more efficient than this solution – Itsik Nov 23 '16 at 04:32
Hello @Itsik, this solution isn't much elegant but it's exactly what @mynameisneo wanted: `I also solved the question using LINQ but wanted an additional solution that didn't involve sorting.` Please refer to initial question. – Denys Denysenko Nov 23 '16 at 13:19

jwaliszko · Answer 2 · 2013-04-22T08:06:57.010

As you have asked for more elegant solution, maybe this one fits your needs - more compacted, written as an extension method:

public static bool IsAnagram(this string s1, string s2)
{
    if (s1.Length == s2.Length)
    {
        var count = new int[1024];
        foreach (var c in s1)
        {
            ++count[c];
        }
        return s2.All(t => --count[c] >= 0);
    }
    return false;
}

var result = "mary".IsAnagram("army");

Damien_The_Unbeliever · Answer 3 · 2013-04-22T08:21:35.833

To properly deal with all Unicode characters (since Char represents a UTF-16 code unit), I can't think of an efficient way. But I'll try with a correct one:

public static bool isAnagram(String s, String t)
{
    s = s.Normalize();
    t = t.Normalize();

    if (s == "" || t == "") return false;
    else if (s.Length != t.Length) return false;

    while (s.Length > 0)
    {
        char first = s[0];
        string search = new string(first, 1);
        if (Char.IsHighSurrogate(first))
        {
            char second = s[1]; //Assumed to work - if it doesn't, the input was malformed
            search = new string(new char[] { first, second });
        }
        int index = t.IndexOf(search);
        if (index < 0) return false;
        t = (index > 0 ? t.Substring(0, index) : "") + t.Substring(index + search.Length);
        s = s.Substring(search.Length);
    }
    return true;
}

Otherwise, if you want to continue with using an array of counters (letters), you ought to use an array that can contain at least 1114112 elements, and you still need to properly process surrogates.

score 2 · Answer 4 · answered Apr 22 '13 at 07:32

2

You can sort both strings and compare

answered Apr 22 '13 at 07:32

Itsik

3,920
1
25
37

I have a coded answer that does this, I want a non-sorting option – mynameisneo Apr 22 '13 at 07:33
1

Sorry, didn't see that comment in your question – Itsik Apr 22 '13 at 07:38

Matthew Watson · Answer 5 · 2013-04-22T07:52:05.477

2

How about this non-linq solution?

public static bool IsAnagram(String s, String t)
{
    if ((s == null) || (t == null) || (s.Length == 0) || (t.Length == 0) || (s.Length != t.Length))
        return false;

    var ta = t.ToCharArray();

    foreach (char ch in s)
    {
        int x = Array.IndexOf(ta, ch);

        if (x < 0)
            return false;

        ta[x] = '\0';
    }

    return true;
}

edited Apr 22 '13 at 07:52

answered Apr 22 '13 at 07:44

Matthew Watson

104,400
10
158
276

Matthew, this is pretty sweet, but it returns true with whitespace added (ex: "dog", "god " should ideally return false). – mynameisneo Apr 22 '13 at 07:53
@mynameisneo Not sure what you mean - IsAnagram("god", "dog ") will return false because the lengths differ and the first check will therefore fail and the method will return `false`. – Matthew Watson Apr 22 '13 at 07:55
Sorry Matthew, I didn't see the edited code before I posted my comment – mynameisneo Apr 22 '13 at 07:56
1

Ahh sorry! Yes, I ninja-edited before I saw your comment. ;) – Matthew Watson Apr 22 '13 at 07:57

score 1 · Answer 6 · edited May 23 '17 at 12:17

A dictionary based solution. Decompose each string by counting the char, then do a Dictionary comparaison (note that this method blow my mind):

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine("jon skeet".PermutationOf("jokes net"));
        Console.WriteLine(new[] { 5, 2, 3, 4, 5 }.PermutationOf(new[] { 5, 4, 5, 2, 3 }));
        Console.Read();
    }
}

public static class Extensions
{
    public static bool IsPermutationOf<T>(this IEnumerable<T> source1, IEnumerable<T> source2)
    {
        return source1.IsPermutationOf(source2, EqualityComparer<T>.Default);
    }
    public static bool IsPermutationOf<T>(this IEnumerable<T> source1, IEnumerable<T> source2, EqualityComparer<T> comparer)
    {
        return source1.Decompose(comparer).DictionaryEqual(source2.Decompose(comparer));
    }
    public static Dictionary<T, int> Decompose<T>(this IEnumerable<T> source, EqualityComparer<T> comparer)
    {
        return source.GroupBy(t => t, comparer).ToDictionary(t => t.Key, t => t.Count(), comparer);
    }
    public static bool DictionaryEqual<TKey, TValue>(this IDictionary<TKey, TValue> first, IDictionary<TKey, TValue> second)
    {
        return first.Count == second.Count && !first.Except(second).Any();
    }
}

Note that you can give a custom char equality comparer, for dealing with uppercase/lowercase problematic.

I gone a little further, by renaming IsAnagram, by IsPermutationOf. Works for all kinds of list in fact. Pretty useful and elegant this way.

Mehmet Ataş · Answer 7 · 2013-04-22T08:06:38.773

Check if lengths are equal, if not, they are not anagram
Loop over the chars of t
Check if the current char of t exists in s, if not, they are not anagram
If so remove that char from s

If the result is empty string they are anagram

public static bool isAnagram(String s, String t) {
    if(s.Length != t.Length) 
        return false;

    for(int i = 0; i < t.Length; i++)
    {
        var n = s.IndexOf(t[i]);
        if(n < 0)
            return false;
        s = s.Remove(n, 1);
    }
    return String.IsNullOrEmpty(s);
}

Botz3000 · Answer 8 · 2013-04-22T07:41:14.767

0

Sorting and then comparing the sequence works:

bool isAnagram = "asdf".OrderBy(c => c).SequenceEqual("fdsa".OrderBy(c => c));

Alternatively, you could use a Dictionary<char, int> to keep track of character counts (Unicode chars have more than 256 possible values). Also, you don't need the call to ToArray() before iterating over the characters of a string.

edited Apr 22 '13 at 07:41

answered Apr 22 '13 at 07:34

Botz3000

39,020
8
103
127

To be honest I doubt that, for the size of the strings usually involved, a presort would outperform a stack-based buffer, especially since the sort still needs a `strcmp` afterwards. Would be worth a test hehe. – Niels Keurentjes Apr 22 '13 at 07:40

Given two strings, is one an anagram of the other

8 Answers8