9
\$\begingroup\$

I know this question has been asked before now but in Python. Recently, I set out to write an anagram in C#. For instance, orchestra can be rearranged into carthorse and the anagram should not have more repeated than the original. The function is meant to check if the two words are the same and return true in this case. I started with putting the two words in two separate dictionaries with the letters as a key and the count as value.

The idea is using a dictionary ensures the keys can not be repeated. Then I looped through the second dictionary (secondString) and checked if each letter existed as a key in the first dictionary (firstString). Additionally, if the letter existed, the code checks if they have the same count. The rest of the code is self-explanatory.

using System;
using System.Collections.Generic;

public class AreAnagrams
{
    public static bool AreStringsAnagrams(string a, string b)
    {
        Dictionary<char,int> firstString = new Dictionary<char,int>();
        Dictionary<char,int> secondString = new Dictionary<char,int>();

        foreach(char character in a)
        {
            if(firstString.ContainsKey(character)== true)
            {
                firstString[character]+=1;
            }
            else
                firstString[character]=1;
        }
        foreach(char character2 in b)
        {
            if(secondString.ContainsKey(character2)== true)
            {
                secondString[character2]+=1;
            }
            else
                secondString[character2]=1;
        }

        foreach(KeyValuePair<char,int> letterValue in secondString)
        {
            if(firstString.ContainsKey(letterValue.Key))
            {
                if(firstString[letterValue.Key] != secondString[letterValue.Key]){

                    return false;
                }
            }
            else
            {
                return false;
            }
        }
        //throw new NotImplementedException("Waiting to be implemented.");
        return  true;
    }

    public static void Main(string[] args)
    {
        Console.WriteLine(AreStringsAnagrams("momdad", "dadmom"));
    }
}

But I scored 75% and I feel this can be improved on. Also, is there any easy conversion from string to dictionary?

\$\endgroup\$
  • \$\begingroup\$ Just curious, what gave you a "score" of 75%? Was this a homework assignment or one of those coding academies? Also, you are allowed change the accepted answer if a newer one helps you more. You also have enough points to upvote answers now! \$\endgroup\$ – Zach Mierzejewski May 5 '16 at 19:39
  • \$\begingroup\$ As funny as it sounds Zach, it was one of the coding websites I visited today. \$\endgroup\$ – Siobhan May 5 '16 at 21:42
  • \$\begingroup\$ Hint: Think of a function f such that strings S and T are anagrams if and only if f(S) = f(T) \$\endgroup\$ – Colonel Panic May 6 '16 at 13:51
  • \$\begingroup\$ See stackoverflow.com/a/31705741/284795 \$\endgroup\$ – Colonel Panic May 6 '16 at 13:56

10 Answers 10

6
\$\begingroup\$

I took your new code and cleaned it up a bit by

  • adjusting bracket location
  • removed unnecessary nesting of if statements
  • gave some operations some breathing room
  • fixed some odd indentations

I took your code

using System;
using System.Collections.Generic;

public class AreAnagrams
{
    public static bool AreStringsAnagrams(string a, string b)
    {
      Dictionary<char,int> firstString = new Dictionary<char,int>();
      Dictionary<char,int> secondString = new Dictionary<char,int>();

      foreach(char character in a)
      {
          if(firstString.ContainsKey(character))
          {
              firstString[character]+=1;
          }
          else{
              firstString[character]=1;
              }
      }

      foreach(char character2 in b)
      {
          if(secondString.ContainsKey(character2))
          {
              secondString[character2]+=1;
          }
          else{
              secondString[character2]=1;
              }
      }


      if(firstString.Count !=secondString.Count){
          return false;
      }
      else   {
              foreach(KeyValuePair<char,int> letterValue in secondString)
                  {
                      if(firstString.ContainsKey(letterValue.Key))
                      {
                          if(firstString[letterValue.Key] != secondString[letterValue.Key]){

                              return false;
                              }
                      }
                      else
                      {
                          return false;
                      }
                  }
              }
      return  true;
  }

  public static void Main(string[] args)
  {
      Console.WriteLine(AreStringsAnagrams("momdad", "dadmom"));
  }
}

and refactored it to this (there is an issue with the if then statement inside last for loop, which I address later)

public class AreAnagrams
{
    public static bool AreStringsAnagrams(string a, string b)
    {
        Dictionary<char,int> firstString = new Dictionary<char,int>();
        Dictionary<char,int> secondString = new Dictionary<char,int>();

        foreach(char character in a)
        {
            if(firstString.ContainsKey(character))
            {
                firstString[character] += 1;
            }
            else
            {
                firstString[character] = 1;
            }
        }

        foreach(char character2 in b)
        {
            if(secondString.ContainsKey(character2))
            {
                secondString[character2] += 1;
            }
            else
            {
                secondString[character2] = 1;
            }
        }

        if(firstString.Count != secondString.Count)
        {
            return false;
        }
        else   
        {
            foreach(KeyValuePair<char,int> letterValue in secondString)
            {
                if(firstString.ContainsKey(letterValue.Key) 
                    && (firstString[letterValue.Key] != secondString[letterValue.Key]))
                {
                    return false;
                }
                else
                {
                    return false;
                }
            }
        }
        return  true;
    }

    public static void Main(string[] args)
    {
        Console.WriteLine(AreStringsAnagrams("momdad", "dadmom"));
    }
}

I also decided to change this so that there are two separate if statements, this will reduce the O(n) in the optimistic case (Your code cleaned up)

foreach(KeyValuePair<char,int> letterValue in secondString)
{
    if(firstString.ContainsKey(letterValue.Key))
    {
        if(firstString[letterValue.Key] != secondString[letterValue.Key]){
            return false;
        }
    }
    else
    {
        return false;
    }
}

New Code with less complexity

foreach(KeyValuePair<char,int> letterValue in secondString)
{
    if (!firstString.ContainsKey(letterValue.Key))
    {
        return false;
    }
    if (firstString[letterValue.Key] != secondString[letterValue.Key])
    {
        return false;
    }
}

You could merge these into a single if statement, but for the sake of reading I left them separate here.

If one doesn't contain the key of the other one, you want to return false, no need to check the other condition.


Another overall thing that you could do to reduce the O(n) is to evaluate if the strings are the same length, immediately and return false if they are not, because you already know they cannot be anagrams of each other.

like this

using System;
using System.Collections.Generic;

public class AreAnagrams
{
    public static bool AreStringsAnagrams(string a, string b)
    {
        if (a.Length != b.Length) {
            return false;
        }

        Dictionary<char,int> firstString = new Dictionary<char,int>();
        Dictionary<char,int> secondString = new Dictionary<char,int>();

       /// ...

then you can remove the check later in the code.

I did that, and also changed += 1 to ++ twice in your code. I also made it case insensitive, but sentences will not work.

Here is the code that works, I tested with your example and with Joker and JReko

if (a.Length != b.Length)
{
    return false;
}

Dictionary<char, int> firstString = new Dictionary<char, int>();
Dictionary<char, int> secondString = new Dictionary<char, int>();

foreach (char character in a.ToLower())
{
    if (firstString.ContainsKey(character))
    {
        firstString[character]++;
    }
    else
    {
        firstString[character] = 1;
    }
}

foreach (char character2 in b.ToLower())
{
    if (secondString.ContainsKey(character2))
    {
        secondString[character2]++;
    }
    else
    {
        secondString[character2] = 1;
    }
}

foreach (KeyValuePair<char, int> letterValue in secondString)
{
    if (!firstString.ContainsKey(letterValue.Key)
        || (firstString[letterValue.Key] != secondString[letterValue.Key]))
    {
        return false;
    }
}

return true;
\$\endgroup\$
  • 1
    \$\begingroup\$ This looks better to be honest \$\endgroup\$ – Siobhan May 5 '16 at 16:09
  • \$\begingroup\$ @TolaniJaiye-Tikolo, I added some thoughts about making the method more efficient. and thank you. \$\endgroup\$ – Malachi May 5 '16 at 16:14
  • \$\begingroup\$ although this leaves capitalization unchecked \$\endgroup\$ – Malachi May 5 '16 at 17:26
  • \$\begingroup\$ so "JReko" is not an anagram of "Joker" \$\endgroup\$ – Malachi May 5 '16 at 17:27
  • 2
    \$\begingroup\$ You can make this code simpler if you use 1 dictionary instead of 2. Add characters from the first string, subtract from the second, anything that reaches 0 gets removed, and at the end, just check that you have 0 items in your dictionary. \$\endgroup\$ – Bryce Wagner May 5 '16 at 23:23
5
\$\begingroup\$

There seems to be a lot of answers but not much explaining why one would be better than the others. Generally when improving on a solution, you either want to cut down on memory usage or execution time. Memory usage is pretty easy to track and in Computer Science we have Big-O notation to figure out worst case execution time.

I'll preface this with I'm doing this all in my head so I maybe off here and there.

So lets take the final code that Malachi provided and first go through worst case execution time.

  1. Populating firstString dictionary - O(n)
  2. Populating secondString dictionary - O(n)
  3. Then we iterate over the second dictionary - O(n)
  4. Do a look up in the dictionary - O(1) And finally return

So execution wise this is O(3n) which would just simplify down to O(n)

Memory wise we are creating a lot of pointers here. Each dictionary is a pointer, the pointer to the key and the pointer to the value are all either 32bit or 64bit depending on your .Net system. Then the iteration of the KeyValuePair creates yet another pointer along with some underlying logic to create the class that holds those values (I'm too lazy to go look up the open source code).

Overall we have

  • 1 pointer for each dictionary
  • n pointers for each character in the key
  • n pointers for the values
  • n char (which is an int)
  • n int And all that multiplied by 2 since we have two of them

So on a 64 bit machine where pointers are 8 bytes and ints are 4 bytes this ends up being 2 * (8 + 8*n + 8*n + 4*n + 4*n) and this doesn't even include the creation of the KeyValuePair stuff.

Now lets take a look at something that maybe a bit less execution efficient but likely more memory efficient.

public static bool AreStringsAnagrams(string a, string b)
{
    if (a == b)
    {
        return true;
    }
    if (a == null || b == null)
    {
        return false;
    }
    if (a.Length != b.Length)
    {
        return false;
    }

    var charInA = a.ToCharArray();
    var charInB = b.ToCharArray();

    Array.Sort(charInA);
    Array.Sort(charInB);

    for (int i = 0; i < charInA.Length; i++)
    {
        if (charInA[i] != charInB[i])
        {
            return false;
        }
    }

    return true;
}
static void Main(string[] args)
{
    Console.Out.WriteLine(AreStringsAnagrams("orchestra", "carthorse"));
    Console.ReadKey();
}

So worst case run time here would be:

  1. Copy all characters in string a to array - O(n)
  2. Copy all characters in string b to array - O(n)
  3. Sort charInA - O(nlog(n))
  4. Sort charInb - O(nlog(n))
  5. Iterate through both sorted arrays and see if there are any differences - O(n)

Memory would be the following:

  1. Copy all characters in string a to array - n * 4 bytes
  2. Copy all characters in string b to array - n * 4 bytes Total 8 * n bytes.

So it all depends on what you want to optimize here memory or time.

And there are ways of combining both solutions, for example:

public static bool AreStringsAnagrams(string a, string b)
{
    if (a == b)
    {
        return true;
    }
    if (a == null || b == null)
    {
        return false;
    }
    if (a.Length != b.Length)
    {
        return false;
    }

    Dictionary<char, int> firstString = new Dictionary<char, int>();
    foreach (char character in a)
    {
        if (firstString.ContainsKey(character))
        {
            firstString[character]++;
        }
        else
        {
            firstString[character] = 1;
        }
    }

    for (int i = 0; i < b.Length; i++)
    {
        if (!firstString.ContainsKey(b[i]))
        {
            return false;
        }
        else
        {
            firstString[b[i]]--;
        }

        if (firstString[b[i]] < 0)
        {
            return false;
        }
    }

    return true;
}

which reduces the number of dictionaries to 1 but still maintains an O(n) worst case runtime.

Data collections are useful but tend to be memory intensive if used incorrectly. Just something to keep in mind :-).

Also broader community, it's pretty easy to see when someone is posting a homework assignment. I'm posting this larger analysis because the poster said they already got a 100%. Is there a policy regarding doing other peoples homework questions on this site? Seems like we should guide people to the answer in that situation, not give them the answer... or else I wouldn't have learned anything in university!

\$\endgroup\$
  • \$\begingroup\$ I'm not sure I understand. The equality operator will only verify if the two strings are the exact same string or both null. The null check after the a == b is to test if one is null and the other is not (because a==b would have tested if they were both null) and the length check is again if they are not the exact same string. \$\endgroup\$ – k2snowman69 May 7 '16 at 6:19
4
\$\begingroup\$

It looks like you got your answer for making it more efficient. Here is how you can use LINQ to make your code (in my opinion) more concise, safer, and more readable.

To create a dictionary with the count of each letter, you can group a collection of letters by their value, get each group's count, and then convert the result into a dictionary:

Dictionary<char,int> firstString = a.GroupBy(x => x).ToDictionary(g => g.Key, g => g.Count());

The body of the foreach loop that helps determine if the strings are anagrams can be condensed into one if statement:

if(!firstString.ContainsKey(letterValue.Key) ||
   firstString[letterValue.Key] != secondString[letterValue.Key])
{
    return false;
}

You can actually replace that foreach loop and the if statement above it with code similar to this answer to determine if two dictionaries are equal:

return firstString.Count == secondString.Count && !firstString.Except(secondString).Any();

Edit: You can check if the strings are the same length right away to avoid doing extra work when they aren't. Thanks to JonathanR for the suggestion.

The class then looks like this:

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

public class AreAnagrams
{
    public static bool AreStringsAnagrams(string a, string b)
    {
        if(a.Count() != b.Count())
        {
            return false;
        }
        Dictionary<char,int> firstString = a
            .GroupBy(x => x)
            .ToDictionary(g => g.Key, g => g.Count());
        Dictionary<char,int> secondString = b
            .GroupBy(x => x)
            .ToDictionary(g => g.Key, g => g.Count());
        return firstString.Count == secondString.Count &&
               !firstString.Except(secondString).Any();
    }

    public static void Main(string[] args)
    {
        Console.WriteLine(AreStringsAnagrams("momdad", "dadmom"));
    }
}

If you want, you can extract the code that converts a string to a dictionary into a method, since it's used twice. Because the string lengths are checked right away, firstString.Count == secondString.Count && is not necessary if you want to leave that out.

Edit 2: k2snowman69 pointed out that you could sacrifice some speed for less memory usage by avoiding dictionaries and instead sorting both strings and comparing each character in sequence. Now I have an excuse to post this solution, which not only does that, but is shorter and a lot more readable:

public static bool AreStringsAnagrams(string a, string b)
{
    return a.Count() == b.Count() && a.OrderBy(x => x).SequenceEqual(b.OrderBy(x => x));
}
\$\endgroup\$
  • \$\begingroup\$ You're counting after aggregating rather than before so it's still O(n) for really long strings of different lengths. \$\endgroup\$ – JonathanR May 5 '16 at 15:57
  • \$\begingroup\$ @JonathanR Good catch! I updated my answer. \$\endgroup\$ – Risky Martin May 5 '16 at 18:48
3
\$\begingroup\$

How about this:

bool AreAnagrams(string a, string b)
{
    return Enumerable.SequenceEqual(
        a.Normalize(NormalizationForm.FormC).OrderBy(c => c),
        b.Normalize(NormalizationForm.FormC).OrderBy(c => c));
}

Shorter and very readable. First it normalizes the string, which solves the issue raised in RobH's answer. Then it arranges the characters of each string into alphabetical order, which should return the same sequence for both strings if they are anagrams. Finally it compares those two sequences.

Your original attempt, and a lot of these answers, seem to involve a hell of a lot of code. I would suggest that unless you're looking for micro-optimised performance, this is a good implementation.

\$\endgroup\$
2
\$\begingroup\$

After adding a little detail based on Jonathan's help. The full code is

using System;
using System.Collections.Generic;

public class AreAnagrams
{
    public static bool AreStringsAnagrams(string a, string b)
    {
        Dictionary<char,int> firstString = new Dictionary<char,int>();
        Dictionary<char,int> secondString = new Dictionary<char,int>();

        foreach(char character in a)
        {
            if(firstString.ContainsKey(character))
            {
                firstString[character]+=1;
            }
            else{
                firstString[character]=1;
                }
        }

        foreach(char character2 in b)
        {
            if(secondString.ContainsKey(character2))
            {
                secondString[character2]+=1;
            }
            else{
                secondString[character2]=1;
                }
        }


        if(firstString.Count !=secondString.Count){
            return false;
        }
        else   {
                foreach(KeyValuePair<char,int> letterValue in secondString)
                    {
                        if(firstString.ContainsKey(letterValue.Key))
                        {
                            if(firstString[letterValue.Key] != secondString[letterValue.Key]){

                                return false;
                                }
                        }
                        else
                        {
                            return false;
                        }
                    }
                }
        return  true;
    }

    public static void Main(string[] args)
    {
        Console.WriteLine(AreStringsAnagrams("momdad", "dadmom"));
    }
}
\$\endgroup\$
  • \$\begingroup\$ If you want to post your new code as a result of improvements, I agree it should be Community Wiki. \$\endgroup\$ – TheCoffeeCup May 5 '16 at 15:20
  • \$\begingroup\$ How do I do make it a community Wiki guys \$\endgroup\$ – Siobhan May 5 '16 at 15:24
  • 1
    \$\begingroup\$ your Brackets are all over the place, makes it hard to read. you should be consistent with your brackets \$\endgroup\$ – Malachi May 5 '16 at 15:47
2
\$\begingroup\$

An example of the sort of structural change Risky Martin suggested.

If you want, you can extract the code that converts a string to a dictionary into a method, since it's used twice.

Your lines 11-19:

foreach(char character in a)
{
    if(firstString.ContainsKey(character)== true)
    {
        firstString[character]+=1;
    }
    else
        firstString[character]=1;
}

lines 20-28:

foreach(char character2 in b)
{
    if(secondString.ContainsKey(character2)== true)
    {
        secondString[character2]+=1;
    }
    else
        secondString[character2]=1;
}

See how similar these are? A pretty sound principle is to not have repeat blocks of code like this. Instead you can take all the only-slightly-differing parts of code (watch for variables with similar names), make them generic, add some declarations and put the block into a new function. Then you get:

public static Dictionary<char, int> newFunction(string z)
{
    Dictionary<char, int> z = new Dictionary<char, int>();
    foreach(char y in x)
    {
        if(z.ContainsKey(y)== true)
        {
            z[y]+=1;
        }
        else
            z[y]=1;
    }
    return z;
}

I'd advise (for readability) against leaving such generic variable names in place, and you should pick a meaningful function name (I originally was going to use "countChars()" but that sorta sounded like it was just going to count the total number of characters - find your own balance between ambiguous names and overly specific/long names). So I'd actually render this as:

public static Dictionary<char, int> tallyByDistinctChar(string characters)
{
    Dictionary<char, int> numChars = new Dictionary<char, int>();
    foreach (char c in characters)
    {
        if (numChars.ContainsKey(c))
            numChars[c] += 1;
        else
            numChars[c] = 1;
    }
    return numChars;
}

Or I might condense it by using a ternary (the " ? : " construct) because it easily fits on one line:

public static Dictionary<char, int> tallyByDistinctChar(string characters)
{
    Dictionary<char, int> numChars = new Dictionary<char, int>();
    foreach (char c in characters)
        numChars[c] = numChars.ContainsKey(c) ? (numChars[c] + 1) : 1;

    return numChars;
}

Which turns the whole code into:

using System;
using System.Collections.Generic;

public class AreAnagrams
{
    public static Dictionary<char, int> tallyByDistinctChar(string characters)
    {
        Dictionary<char, int> numChars = new Dictionary<char, int>();
        foreach (char c in characters)
            numChars[c] = numChars.ContainsKey(c) ? (numChars[c] + 1) : 1;

        return numChars;
    }

    public static bool AreStringsAnagrams(string a, string b)
    {
        Dictionary<char, int> firstString = tallyByDistinctChar(a);
        Dictionary<char, int> secondString = tallyByDistinctChar(b);

        foreach(KeyValuePair<char,int> letterValue in secondString)
        {
            if(firstString.ContainsKey(letterValue.Key))
            {
                if(firstString[letterValue.Key] != secondString[letterValue.Key]){

                    return false;
                }
            }
            else
            {
                return false;
            }
        }
        //throw new NotImplementedException("Waiting to be implemented.");
        return  true;
    }

    public static void Main(string[] args)
    {
        Console.WriteLine(AreStringsAnagrams("momdad", "dadmom"));
    }
}

Then I'd the alter the style of lines 20-35 (and add the length check shortcut) but I've left the rest of your code as is for clarity/contrast.

Something else to think about: Do you want to consider a string to be it's own anagram?

\$\endgroup\$
  • \$\begingroup\$ Very Nice Review. Welcome to Code Review! \$\endgroup\$ – Malachi May 5 '16 at 17:53
2
\$\begingroup\$

Without changing the heart of your program, I refactored/rewrote it down to this

public static bool AreStringsAnagrams(string a, string b)
{
    var firstString = a.GroupBy(val => val).ToDictionary(letter => letter.Key, letter => letter.Count());
    var secondString = b.GroupBy(val => val).ToDictionary(letter => letter.Key, letter => letter.Count());


    foreach (var kvp in firstString)
        if (!secondString.ContainsKey(kvp.Key) || secondString[kvp.Key] != kvp.Value)
            return false;

    return firstString.Keys.Count == secondString.Keys.Count;
}

In your original program, you had some inconsistencies with your usage of brackets, and there were places where you could have condensed your if-statements into single statements. I'm more interested in seeing you learn the power of LinQ.

First two lines are spent creating a dictionary exactly the same as you were before, except using LinQ to do so. First step is taking the list of letters you have (string) and grouping them by their value a.GroupBy(val => val). This returns a collection of IGrouping objects. On this collection, we then call ToDictionary(KeySelector, ValueSelector). For the key I specify, that I want the grouped value letter => letter.Key which is simply the letter its self. For the value, we want how many times that letter was in the original string, which is just the count of that letter in the grouping letter => letter.Count(). Keep in mind in both of these selectors, that the letter value is the IGrouping object.

After that I run through the firstString, and check to make sure that every key that is in the first dictionary, is also in the second dictionary. When I confirm that, I ensure that their values (counts) are the same. If at some point, this is not true, I simply return false at that moment.

After all that, we know the first string is at-least contained in the second one, but we don't know if the second string perhaps has additional other characters. If we just returned true right now, it is possible that a = "hi", b = "hiaaaaa" would return true. So all we have to do, is make sure that they key count is the same, that way we know there are no more other letters, and we know we've already verified that the counts of the ones that do exist in the first string are valid, so just a key count comparison is all we need.


If you were looking reduce the amount of code further, you could probably skip the whole dictionary part of this, and just compare the lists returned from the GroupBy, by intersecting them and subtracting one list from the other.

I just had to try :)

public static bool AreStringsAnagrams(string a, string b)
{
    return     a.GroupBy(val => val).Select(letter => new { Letter = letter.Key, Count = letter.Count() })
        .Union(b.GroupBy(val => val).Select(letter => new { Letter = letter.Key, Count = 0 - letter.Count() }))
        .GroupBy(letters => letters.Letter)
        .Where(letters => letters.Sum(letter => letter.Count) != 0)
        .Count() == 0;
}

In this alternate solution, you'll notice that I use LinQ to Union the two lists. For the second list, you may also see that I set the count to be negative, so when I re-grouped them again and did a sum of their Count values, they would subtract from each other. Then after that I do a Where checking for anything that wasn't zero'd out by the subtraction. Then return whether or not the collection contains any of those.

\$\endgroup\$
  • \$\begingroup\$ Your final solution is lovely! A quick note - you need to use a case insensitive comparison in the GroupBy or things like Abc and Cba will return false but really they are anagrams. \$\endgroup\$ – RobH May 6 '16 at 10:33
  • 1
    \$\begingroup\$ Thanks! To add case sensitivity, there would just need to be initial ToLower calls on the strings before the grouping. a.ToLower().GroupBy( \$\endgroup\$ – BenVlodgi May 6 '16 at 13:27
1
\$\begingroup\$

Most of these suggestions are style-based, but I think they can be helpful to you either way.

Code Consistency

Your if-statements have a mix of inconsistencies.

  1. Always use brackets. Even if the statement afterward is a one-liner just use them, it'll prevent a rookie mistake in the future. Secondly, if you insist on not using brackets, be consistent. You have an if-statement with brackets and the else-statement doesn't.
  2. Curley bracket placement. The standard for C# is placing brackets on their own line. You have spots where you do this, but you also have spots where you place the opening curley bracket on the same line as the if-statement.

Efficiency

  1. As JonathanR suggested, check if their lengths match, if not then there is no point in doing all that other work.
\$\endgroup\$
  • \$\begingroup\$ I don't know what your first point under "efficiency" has to do with being efficient. Your second point is questionable as well -- it all depends on the kind of enumerator, collection, element type, etc. \$\endgroup\$ – Jeroen Vannevel May 5 '16 at 14:17
  • \$\begingroup\$ The first point theoretically would be faster dropping the == true but yes the compiler almost definitely optimizes this away. \$\endgroup\$ – Shelby115 May 5 '16 at 15:02
  • \$\begingroup\$ There is no theoretically -- it's literally the exact same thing. They translate to the same IL so there will never be a difference. \$\endgroup\$ – Jeroen Vannevel May 5 '16 at 17:27
  • \$\begingroup\$ I just said "the compiler almost definitely optimizes this away" what I meant by the theoretically is that it's 2 boolean conditions instead of just one (that the contains function returns). Never the less, I deleted the suggestion anyways. \$\endgroup\$ – Shelby115 May 5 '16 at 17:37
1
\$\begingroup\$

A Bug!

It's always fun to point out edge cases when everyone starts thinking that you can reliably process a string as an array of characters. I'll chose a simple one - I'll pass the same word as both strings and show that all of the answers on this page return the incorrect answer.

What's my test case? café

E-acute is an amazing letter - it can be represented as a single char in .Net ((char)233) == 'é' but it can also be two char instances: 'e' and '\x0301' (e and the combining acute accent character).

Armed with that knowledge - let's plug it in:

var cafe1 = "café";
var cafe2 = "cafe\x0301";
Console.WriteLine(cafe1);
Console.WriteLine(cafe2);
Console.WriteLine(AreStringsAnagrams(cafe1, cafe2));

That will print:

café
café
False

Are these kinds of edge cases important? Probably not if you're only interested in input that you control that you know isn't trying to deliberately trip you up (unlike me). It is worth knowing that they exist though!

\$\endgroup\$
  • \$\begingroup\$ Please could you speak with clearer terms RobH with examples relating to the anagram problem \$\endgroup\$ – Siobhan May 6 '16 at 14:29
  • \$\begingroup\$ @TolaniJaiye-Tikolo - "café" and "café" are the same word so AreStringsAnagrams should return true. That's not the case, so the implementation has a bug. Which bit are you struggling to follow? \$\endgroup\$ – RobH May 6 '16 at 14:42
  • \$\begingroup\$ @TolaniJaiye-Tikolo - Just to be clear: I was asking which part of the answer was unclear so I could expand the detail. Reading my comment back it sounds a bit rude/hostile (which isn't at all how I meant it!) \$\endgroup\$ – RobH May 6 '16 at 15:42
  • \$\begingroup\$ Hey, not all the answers on this page have the bug! ;) Just so you know, my answer (codereview.stackexchange.com/a/127698/104788) doesn't have this bug. \$\endgroup\$ – Richard Irons May 6 '16 at 15:52
0
\$\begingroup\$

First, check if the strings are the same length, if not return false.

\$\endgroup\$

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.