I have 2 string for example "abcdefg" "bcagfed" I want to write a method that determine these two strings are equal

*sorted or unsorted is not matter. In my example my above strings are equal.

One answer is: before checking equality, sort them and after that easily can check equality but this is not the fastest way

CodePudding user response：

Here's one way to do it without sorting first, and without using anything fancy like LINQ:

string str1 = "abcdefg";
string str2 = "bcagfed";

bool stringsAreEqual = (str1.Length == str2.Length);
if (stringsAreEqual)
{
    // see if each char from str1 is in str2, removing from str2 as we go
    List<char> str2chars = new List<char>(str2.ToCharArray());
    foreach (char c in str1.ToCharArray())
    {
        int index = str2chars.IndexOf(c);
        if (index != -1)
        {
            str2chars.RemoveAt(index);
        }
        else
        {
            stringsAreEqual = false;
            break;
        }
    }
    // any chars left over in str2?
    stringsAreEqual = stringsAreEqual && (str2chars.Count == 0);
}            

Console.WriteLine(str1);
Console.WriteLine(str2);
Console.WriteLine(stringsAreEqual);

CodePudding user response：

I prefer using SequenceEqual, it checks whether the two source sequences are of equal length and their corresponding elements are equal.

var str1 = "abcdefg"; 
var str2 = "bcagfed";

var areEqual = Enumerable.SequenceEqual(str1.OrderBy(c => c), str2.OrderBy(c => c));

CodePudding user response：

As others have pointed out, the easiest way is to sort then compare.

For academic interest, here's a way of doing it without sorting:

public static bool StringsContainSameChars(string s1, string s2)
{
    var lookup1 = s1.ToLookup(ch => ch); // O(N)
    var lookup2 = s2.ToLookup(ch => ch); // O(N)

    return lookup1.All(keyValue => // O(N)
        lookup2.Contains(keyValue.Key) && keyValue.Count() == lookup2[keyValue.Key].Count());
}

In theory this is an O(N) operation, but it would have a huge overhead and is likely to be slower than the obvious sorting approach. If N was very large, then this would in theory be faster.

Note: I'm saying this is O(N) because:

• Enumerable.ToLookup() is an O(N) operation
• Lookup<TKey,TElement>.Contains() is an O(1) operation.
• The Lookup<TKey,TElement> indexer ([]) is an O(1) operation.
• keyValue.Count() will be an O(1) operation even though it's using Linq.Count(), because the underlying type implements ICollection<T> which allows Linq to perform the shortcut of using the .Count property.

Therefore the overall complexity is O(N).

But like I say, this is really of academic interest only.