13

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;
}
7

17 Answers 17

22

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))) ...
6
  • 1
    Concise but not very efficient? (O n log n?)
    – Rawling
    Sep 25, 2015 at 8:53
  • 1
    No, it is not his solution and his solution is better.
    – Andrey
    Sep 25, 2015 at 8:57
  • 4
    You can do the same thing even shorter: var isAnagram = a.OrderBy(c => c).SequenceEqual(b.OrderBy(c => c));
    – Kvam
    Sep 25, 2015 at 9:02
  • I did no check for 500k strings, because I do not believe it is a real live setting Sep 25, 2015 at 9:09
  • for big strings I´ll test something on the Weekend Sep 25, 2015 at 9:10
9

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;
}
7
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;
}
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.

2
  • For Linq approach will not work correctly in cases "ab" and "a". Since they don't check the same length, please check sir.
    – jack.pop
    Jun 7, 2022 at 3:10
  • 1
    I think you should keep the first condition if(a.Length != b.Length) return false; for linq approach too. @jack.pop Jun 11, 2022 at 13:43
4

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;
    }
2
  • Why do you need this line bucket[aOrb] += j;?
    – bck
    Sep 11, 2021 at 21:15
  • 1
    The idea is to use a dictionary to find different characters in the two strings. In the loop, we get two characters: one from s1 and another one from s2. Then for characters from s1 we add -1 to the corresponding dictionary entry and +1 for the characters from s2. If the result is 0, then we remove the entry from the dictionary. It is also possible to not remove the entry from the dictionary but, in the end, check the dictionary so it does not have any none zero entries.
    – Alex
    Sep 30, 2021 at 7:38
3
    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();
    }
2

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;
}
2

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;
    }
1
    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));
    }
0
0

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));
    }
0

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;          
        }
0

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;
}
0
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;
2
  • 1
    you should add a little more context to your answer instead of just posting the code. Nov 22, 2019 at 13:33
  • How is this any different from the already provided answer? Nov 22, 2019 at 13:34
0

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))) ...

-1

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;

}
2
  • 3
    Welcome to Stack Overflow. Please review the How to Answer section. Now, are you sure this solution is O(n)? What's the complexity of the sorting methods?
    – compor
    Feb 10, 2018 at 17:30
  • Not different from already given answers. Nov 22, 2019 at 13:38
-1
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("-");
        }
    }
}
0
-1
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;
        }
1
  • While this code snippet may solve the problem, it doesn't explain why or how it answers the question. Please include an explanation for your code, as that really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion. You can use the edit button to improve this answer to get more votes and reputation! Aug 16, 2020 at 21:39

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.