Find How many times an Anagram is contained in a String - asp.net c#

I need to find how many times the Anagrams are contained in a String like in this example:(the anagrams and the string itself)

Input 1(String) = thegodsanddogsweredogged

Input 2(String) = dog

Output(int) = 3 the output will be 3 because of these - (thegodsanddogsweredogged)

So far i managed to check how many times the word "dog" is contained in the string:

        public ActionResult FindAnagram (string word1, string word2)
        {
            int ?count = Regex.Matches(word1, word2).Count;

            return View(count);
        }

This works to check how many times the word is contained but i still get an error: Cannot convert null to 'int' because it is a non-nulable value type.

So i need to check for how many times input 2 and the anagrams of input 2(dog,god,dgo,ogd etc) are contained in input 1?(int this case its 3 times-thegodsanddogsweredogged)

Thank you

2 answers

  • answered 2020-03-31 13:05 Anton

    It would be better not to try to use Regex but write your own logic.

    You can use a dictionary with key char - a letter of the word and value int - number of letter occurrences. And build such a dictionary for the word.

    Anagrams will have similar dictionaries, so you can build a temp dictionary for each temp string built using the Windowing method over your str and compare it with the dictionary built for your word.

    Here is my code:

    using System;
    using System.Collections.Generic;
    
    namespace ConsoleApp1
    {
        class Program
        {
            static void Main(string[] args)
            {
    
                var str = "thegodsanddogsweredogged";
                var word = "dog";
                Console.WriteLine("Word: " + word);
                Console.WriteLine("Str: " + str);
                Console.WriteLine();
    
                var count = CountAnagrams(str, word);
                Console.WriteLine("Count: " + count);
    
                Console.ReadKey();
            }
    
    
            private static int CountAnagrams(string str, string word) {
                var charDict = BuildCharDict(word);
                int count = 0;
    
                for (int i = 0; i < str.Length - word.Length + 1; i++) {
                    string tmp = "";
                    for (int j = i; j < str.Length; j++) {
                        tmp += str[j];
                        if (tmp.Length == word.Length)
                            break;
                    }
    
                    var tmpCharDict = BuildCharDict(tmp);
    
                    if (CharDictsEqual(charDict, tmpCharDict)) {
                        count++;
                        Console.WriteLine("Anagram: " + tmp);
                        Console.WriteLine("Index: " + i);
                        Console.WriteLine();
                    }
    
                }
    
    
                return count;
            }
    
            private static Dictionary<char, int> BuildCharDict(string word) {
                var charDict = new Dictionary<char, int>();
                foreach (var ch in word)
                {
                    if (charDict.ContainsKey(ch))
                    {
                        charDict[ch] += 1;
                    }
                    else
                    {
                        charDict[ch] = 1;
                    }
                }
    
                return charDict;
            }
    
            private static bool CharDictsEqual(Dictionary<char, int> dict1, Dictionary<char, int> dict2) 
            {
                if (dict1.Count != dict2.Count)
                    return false;
    
                foreach (var kv in dict1) {
                    if (!dict2.TryGetValue(kv.Key, out var val) || val != kv.Value)
                    {
                        return false;
                    }
                }
    
                return true;
            } 
        }
    }
    

    Possibly there is a better solution, but mine works.

    P.S. About your error. You should change int? to int, because your View might expect non-nullable int type

  • answered 2020-03-31 14:01 Flater

    I wanted to post a variation which is more readable at the cost of some runtime performance. Anton's answer is probably more performant, but IMHO less readable than it could be.

    The nice thing about anagrams is that you know their exact length, and you can figure out all possible anagram locations quite easily. For a 3 letter anagram in a 100 letter haystack, you know that there are 98 possible locations:

    • 0..2
    • 1..3
    • 2..4
    • ...
    • 96..98
    • 97..99

    These indexes can be generated quite easily:

    var amountOfPossibleAnagramLocations = haystack.Length - needle.Length + 1;
    
    var substringIndexes = Enumerable.Range(0, amountOfPossibleAnagramLocations);
    

    At this point, you simply take every listed substring and test if it's an anagram.

    var anagramLength = needle.Length;
    int count = 0;
    
    foreach(var index in substringIndexes)
    {
        var substring = haystack.Substring(index, anagramLength);
    
        if(substring.IsAnagramOf(needle))
            count++;
    }
    

    Note that a lot of this can be condensed into a single LINQ chain:

    var amountOfPossibleAnagramLocations = haystack.Length - needle.Length + 1;
    var anagramLength = needle.Length;
    
    var anagramCount = Enumerable
                          .Range(0, amountOfPossibleAnagramLocations)
                          .Select(x => haystack.Substring(x, anagramLength))
                          .Count(substring => substring.IsAnagramOf(needle));
    

    Whether it's more readable or not depends on how comfortable you are with LINQ. I personally prefer it (up to a reasonable size, of course).


    To check for an anagram, simply sort the characters and check for equality. I used an extension method for the readability bonus:

    public static bool IsAnagramOf(this string word1, string word2)
    {
        var word1Sorted = String.Concat(word1.OrderBy(c => c));
        var word2Sorted = String.Concat(word2.OrderBy(c => c));
    
        return word1Sorted == word2Sorted;
    }
    

    I've omitted things like case insensitivity or ignoring whitespace for the sake of brevity.