How can check anagram strings in C#

Question

Given two strings A and B, check if they are anagrams.

Two strings are said to be anagrams, if one string can be obtained by rearranging the letters of another.

Examples of anagrams are

• dog, god
• abac, baac
• 123, 312

abab, aaba and dab, baad are not anagrams.

INPUT :

First line of the input is the number of test cases T. It is followed by T lines, each line has two space separated strings A and B;

OUTPUT

For each test case, print "YES" if they are anagrams, otherwise print "NO". (without quotes)

Constraints

1. 1 <= T <= 10
2. A and B both contain only lower case latin letters 'a' to 'z' and digits 0 to 9.
3. Length of each string A and B does not exceed 5*10^5 (500000)

`

Sample Input            Sample Output
------------------------------------
3                           YES
abcd bcda                   NO
bad daa                     YES
a1b2c3 abc123               NO

How can we do this ?

bool anagramChecker(string first, string second)
{
    if(first.Length != second.Length)
        return false;

    if(first == second)
        return true;//or false: Don't know whether a string counts as an anagram of itself

    Dictionary<char, int> pool = new Dictionary<char, int>();
    foreach(char element in first.ToCharArray()) //fill the dictionary with that available chars and count them up
    {
        if(pool.ContainsKey(element))
            pool[element]++;
        else
            pool.Add(element, 1);
    }
    foreach(char element in second.ToCharArray()) //take them out again
    {
        if(!pool.ContainsKey(element)) //if a char isn't there at all; we're out
            return false;
        if(--pool[element] == 0) //if a count is less than zero after decrement; we're out
            pool.Remove(element);
    }
    return pool.Count == 0;
}

Answer 1

Is this your solution?

string a = "abcd";
string b = "bcda"; // bad daa a1b2c3 abc123

string aa = String.Concat(a.OrderBy(c => c));
string bb = String.Concat(b.OrderBy(c => c));

if (aa == bb)
{
     Console.WriteLine("YES");
}
else
{
     Console.WriteLine("NO");
}

or shorter

if (String.Concat(a.OrderBy(c => c)).Equals(String.Concat(b.OrderBy(c => c))) ...

Answer 2

There's the fast way and the simple way:

void Test()
{
    string a = "abccabccabccabccabccabccabccabccabccabccabccabccabccabccabccabcc";
    string b = "bcacbcacbcacbcacbcacbcacbcacbcacbcacbcacbcacbcacbcacbcacbcacbcac";

    IsAnagramSimple(a, b);
    IsAnagramFast(a, b);
}


private bool IsAnagramSimple(string a, string b)
{
    return a.OrderBy(c => c).SequenceEqual(b.OrderBy(c => c));
}

private bool IsAnagramFast(string a, string b)
{
    if (a.Length != b.Length)
    {
        return false;
    }

    var aFrequency = CalculateFrequency(a);
    var bFrequency = CalculateFrequency(b);

    foreach (var key in aFrequency.Keys)
    {
        if (!bFrequency.ContainsKey(key)) return false;
        if (aFrequency[key] != bFrequency[key]) return false;
    }

    return true;
}

private Dictionary<char, int> CalculateFrequency(string input)
{
    var frequency = new Dictionary<char, int>();
    foreach (var c in input)
    {
        if (!frequency.ContainsKey(c))
        {
            frequency.Add(c, 0);
        }
        ++frequency[c];
    }
    return frequency;
}

Answer 3

public bool IsAnagram(string s1,string s2)
{
  if (s1.Length != s2.Length)
     return false;
  var s1Array = s1.ToLower().ToCharArray();
  var s2Array = s2.ToLower().ToCharArray();

  Array.Sort(s1Array);
  Array.Sort(s2Array);

  s1 = new string(s1Array);
  s2 = new string(s2Array);

  return s1 == s2;
}

Answer 4

Another way is to check if first one contains a char inside second one. then remove that char from first one until no more characters left.

    private bool IsAnagram(string a, string b)
    {
        if (a.Length != b.Length) return false;
        List<char> list1 = a.ToList();
        List<char> list2 = b.ToList();
        for (int i = 0; i < a.Length; i++)
        {
            // try to remove list 1 item from list 2
            // if didn't find any thing to remove. so they are not anagram
            if (!list2.Remove(list1[i])) return false;
        }
        return true; // loop finished successfully. they are anagram
    }

Note that the List<T>.Remove() method returns a bool that specifies if the method was able to remove anything or not.

You can do this all in one line Linq.

List<char> list = "god".ToList();

bool isAnagram = "dog".All(ch => list.Remove(ch));

The Linq method All<char>(Func<char,bool>) will perform the delegate until the Func<char,bool> returns false or until end of query. if the Func return false then All returns false too. otherwise it will return true.

Answer 5

Below is an algorithm without sorting two arrays. Assuming ContainsKey, Add, Remove methods of Dictionary are O(1) then the time complexity for the algorithm is O(N) rather than O(nlogn) for those using Sort.

static bool anagram(string s1, string s2)
    {
        if (s1.Length != s2.Length)
        {
            return false;
        }

        Dictionary<char, int> bucket = new Dictionary<char, int>(50); 
        for (int i = 0; i < s1.Length; i++)
        {               
            if (s1[i] == s2[i]) continue;

            for (int j = -1; j < 2; j = j + 2)
            {
                var aOrb = j == -1 ? s1[i] : s2[i];
                if (bucket.ContainsKey(aOrb))
                {
                    bucket[aOrb] += j;
                    if (bucket[aOrb] == 0)
                    {
                        bucket.Remove(aOrb);
                    }
                }
                else
                {
                    bucket.Add(aOrb, j);
                }
            }
        }

        return bucket.Count == 0;
    }

Answer 6

    static void Main()
    {
        Console.WriteLine(IsAnagram(
            "tom marvolo riddle",
            "i am lord voldemort"));
    }
    static bool IsAnagram(string word, string dest)
    {
        var w = WordSpliter(word);
        var d = WordSpliter(dest);
        return w.Count == d.Count && w.Count == w.Where(x => d.Contains(x)).ToList().Count;
    }
    static List<(char Key, int Count)> WordSpliter(string word)
    {
        return word.Replace(" ", "").ToLower().GroupBy(c => c).Select(x => (
           x.Key,
           Count: x.Count()
       )).ToList();
    }

Answer 7

If you have a constraint of limited time, this is a better/efficient solution:

bool CheckAnagram(string str1, string str2)
{
    if(str1.Length != str2.Length)
        return false;

    if(str1 == str2)
        return true;

    // based on 128 ASCII characeters. 
    // You can change the paramter depending on requirement
    int charLength = 128; 

    int[] counter = new int[charLength];

    for(int i=0; i<str1.Length; i++)
    {
        counter[str1[i]-'a']++;
        counter[str2[i]-'a']--;
    }

    for (int c = 0; c < charLength; c++) 
    {
        if(counter[c] != 0) return false;
    }

    return true;
}

Answer 8

This solution is accepted on codestandard.net

public bool IsAnagram(string one, string two)
    {
        if(one.ToLower().Equals(two.ToLower()))
            return true;
    
        var array1 = one.ToCharArray();
        var array2 = two.ToCharArray();
        
        Array.Sort(array1);
        Array.Sort(array2);
        
        return array1 == array2;
    }

Answer 9

    public static bool IsAnagram(this string a, string b)
    {
        //check the length are not same ? not Anagram
        if (a.Length != b.Length)
            return false;

        // check both the strings are same ? Angram
        if (a == b)
            return true;

        // Sort the characters alphabetically and compare them to one another.
        return a.OrderBy(c => c).SequenceEqual(b.OrderBy(c => c));
    }

Answer 10

This solution will check for anagram for exactly 1 pass (O(Cn) where C = 1)

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

        int i = -1;

        var chars = new Dictionary<char, int> ();

        Func <char, int, int, int> updateCount = (c, side, pdiff) => {
            int count = 0;
            chars.TryGetValue (c, out count);
            var newCount = count + side;
            chars[c] = newCount;
            if (count == 0)
                return pdiff + 1;
            else if (newCount == 0)
                return pdiff - 1;
            else
                return pdiff;
        };

        int diff = 0;
        foreach (var c1 in s1) {
            i++;
            var c2 = s2 [i];

            if (c1 == c2)
                continue;

            diff = updateCount(c1, 1, diff);
            diff = updateCount(c2, -1, diff);
        }

        return diff == 0;
    }
    public static void Main (string[] args)
    {
        string s1 = "asd";
        string s2 = "ads";

        Console.WriteLine (IsAnagram(s1, s2));
    }

Answer 11

For case insensitive you can try this:

public bool IsAnagram(string firstString, string secondString)
        {
            List<char> firstlist = new List<char>();
            firstlist.AddRange(firstString);

            List<char> secondlist = new List<char>();
            secondlist.AddRange(secondString);

            if (secondlist.Count != firstlist.Count)
            {
                return false;
            }

            while (firstlist.Count != 0 && secondlist.Count != 0)
            {
                foreach (var sec in secondlist)
                {
                    foreach (var fir in firstlist)
                    {
                        if (char.ToUpperInvariant(sec) == char.ToUpperInvariant(fir))
                        {
                            firstlist.Remove(fir);
                            break;
                        }
                    }
                    secondlist.Remove(sec);
                    break;
                }
            }
            if (firstlist.Count == secondlist.Count)
                return true;
            return false;          
        }

Answer 12

try this

static bool isAnagrams(string str1,string st)
{
    string str1 = "reaad";
    string str2 = "Daaer";
    char[] t = str1.ToCharArray();
    var kt = t.Distinct();
    string pattern = @"e";
    // Create a Regex  
    Regex rg = new Regex(pattern);
    Console.WriteLine(rg.Match(str1).Value);
    foreach (var item in kt)
    {
        string pat = item.ToString();
        Regex r = new Regex(pat,RegexOptions.IgnoreCase);
        if (r.Matches(str1).Count != r.Matches(str2).Count)
        {
            return false;
        }
    }
    return true;
}

Answer 13

char[] fArr = new char[First.Length];
    char[] sArr = new char[Second.Length];
    fArr = First.ToLower().ToCharArray();
    sArr= Second.ToLower().ToCharArray();

    if (fArr.Length == sArr.Length)
    {
       Array.Sort(fArr);
        Array.Sort(sArr);
    }



    return new string(fArr) == new string(sArr) ? true : false;

Answer 14

I have a solution for a List of Strings (Not just two Strings). If you are interested in it or any other one, you can use it.

Given an array of strings, remove each string that is an anagram of an earlier string, then return the remaining array in stored order.

private static List<string> GencoAnagrams(List<string> textList)
    {
        var listCount = textList.Count;
        if (listCount == 1) return textList;

        for (var j = 1; j < listCount; j++)
        {
            for (var i = 0; i < j; i++)
            {
                if (string.Concat(textList[j].OrderBy(x => x)).Equals(string.Concat(textList[i].OrderBy(y => y))))
                {
                    textList.RemoveAt(j);
                    --listCount;
                    --j;
                    if (listCount == 1) break;
                }
            }
            if (listCount == 1) break;
        }
        return textList;
    }

I also thanks "Thomas Krojer" for his Answer, it was very helpful for me at first.

if (String.Concat(a.OrderBy(c => c)).Equals(String.Concat(b.OrderBy(c => c))) ...

Answer 15

class Anagrams
{
    static void Main()
    {
        // 1
        // Read and sort dictionary
        var d = Read();

        // 2
        // Read in user input and show anagrams
        string line;
        while ((line = Console.ReadLine()) != null)
        {
            Show(d, line);
        }
    }

    static Dictionary<string, string> Read()
    {
        var d = new Dictionary<string, string>();
        // Read each line
        using (StreamReader r = new StreamReader("enable1.txt"))
        {
            string line;
            while ((line = r.ReadLine()) != null)
            {
                // Alphabetize the line for the key
                // Then add to the value string
                string a = Alphabetize(line);
                string v;
                if (d.TryGetValue(a, out v))
                {
                    d[a] = v + "," + line;
                }
                else
                {
                    d.Add(a, line);
                }
            }
        }
        return d;
    }

    static string Alphabetize(string s)
    {
        // Convert to char array, then sort and return
        char[] a = s.ToCharArray();
        Array.Sort(a);
        return new string(a);
    }

    static void Show(Dictionary<string, string> d, string w)
    {
        // Write value for alphabetized word
        string v;
        if (d.TryGetValue(Alphabetize(w), out v))
        {
            Console.WriteLine(v);
        }
        else
        {
            Console.WriteLine("-");
        }
    }
}

Answer 16

O(n) Solution

public bool Anagram(string s , string p)
{
    char[] dS = s.ToCharArray();
    char[] dP = p.ToCharArray();
    Array.Sort(dS);
    Array.Sort(dP);
    string rS = new string(dS);
    string rP = new string(dP);
    return rS == rP;

}

Answer 17

string one = "aabba";
        string two = "bbaaa";
        int check = 0;

        List<char> oneList = one.ToCharArray().ToList();
        List<char> twoList = two.ToCharArray().ToList();

        foreach (var letter in oneList /* the principal */)
        {
            if (twoList.Contains(letter))
            {
                check++;
            }
        }
        if (check == twoList.Count)
        {
            return true;
        }
        else
        {
            return false;
        }