Home > Blockchain >  C# find anagram from a string array of candidates
C# find anagram from a string array of candidates

Time:09-28

My task is to implement a method that could return a correct sublist of anagrams.

Now so far I am having problems with figuring out how can I collect the anagrams in candidates that match word and return it.

This is my code for now:

    public class Anagram
    {
        public string word;

        public Anagram(string sourceWord)
        {
            if (sourceWord is null)
            {
                throw new ArgumentNullException(nameof(sourceWord));
            }

            if (sourceWord.Length == 0)
            {
                throw new ArgumentException(null);
            }

            this.word = sourceWord;
        }

        public string[] FindAnagrams(string[] candidates)
        {
            if (candidates is null)
            {
                throw new ArgumentNullException(nameof(candidates));
            }

            char[] char1 = this.word.ToLower().ToCharArray();
            Array.Sort(char1);
            string newWord1 = new string(char1);
            string newWord2;
            string[] result = new string[candidates.Length];

            for (int i = 0; i < candidates.Length; i  )
            {
                char[] char2 = candidates[i].ToLower().ToCharArray();
                Array.Sort(char2);
                newWord2 = char2.ToString();

                if (newWord1 == newWord2)
                {
                    result[i] = candidates[i];
                }
            }

            return result;
        }
    }

Should I do a second for loop in the if statement or something else.

And by the way how I am doing with my class constructor, It's the first time I am trying to use it and at the end I don't think I called the sourceWord variable correctly..

This is one of my test scenarios I would need to pass later on:

        [TestCase("master", new[] { "stream", "pigeon", "maters" }, ExpectedResult = new[] { "stream", "maters" })]
        [TestCase("listen", new[] { "enlists", "google", "inlets", "banana" }, ExpectedResult = new[] { "inlets" })]
        [TestCase("allergy", new[] { "gallery", "ballerina", "regally", "clergy", "largely", "leading" }, ExpectedResult = new[] { "gallery", "regally", "largely" })]
        public string[] FindAnagrams_Detects_Anagrams(string word, string[] candidates)
        {
            var sut = new Anagram(word);
            return sut.FindAnagrams(candidates);
        }

Unfortunatly, can't use LINQ on this task.

CodePudding user response:

If two words are anagrams, they have the same numbers of same letters:

 art ~ rat ~ tar

we can sort letters within each word and group words by such keys:

 ...
 aaabnn: banana
 aemrst: maters, stream
 ...

Code:

using System.Linq;

...

// Given list of (candidates) word return anagrams
public static IEnumerable<string[]> FindAnagrams(IEnumerable<string> candidates) {
  if (null == candidates)
    throw new ArgumentNullException(nameof(candidates));

  return candidates
    .GroupBy(word => string.Concat(word.OrderBy(c => c)))
    .Where(group => group.Count() > 1)
    .Select(group => group.OrderBy(word => word).ToArray());
}

Demo:

string[] demo = new string[] {
  "stream", "pigeon", "maters",
  "enlists", "google", "inlets", "banana",
  "gallery", "ballerina", "regally", "clergy", "largely", "leading",
  "art", "tar", "rat"
};

string report = string.Join(Environment.NewLine, FindAnagrams(demo)
  .Select(group => string.Join(", ", group)));

Console.Write(report);

Outcome:

maters, stream
gallery, largely, regally
art, rat, tar

Edit: Same idea for FindAnagrams_Detects_Anagrams:

  public string[] FindAnagrams_Detects_Anagrams(string word, string[] candidates) {
    if (word == null || candidates == null)
      return new string[0];

    string[] wordArr =  

    string key = string.Concat(word.OrderBy(c => c)); 

    return candidates
      .Where(w => w != null)
      .Where(w => key == string.Concat(w.OrderBy(c => c)))
      .ToArray(); 
  }  

You can get rid of Linq if you want:

All anagrams:

public static IEnumerable<string[]> FindAnagrams(IEnumerable<string> candidates) {
  if (null == candidates)
    throw new ArgumentNullException(nameof(candidates));

  Dictionary<string, List<string>> groups = 
    new Dictionary<string, List<string>>(StringComparer.OrdinalIgnoreCase);

  foreach (var word in candidates) {
    char[] keyArray = word.ToCharArray();

    Array.Sort(keyArray);

    string key = string.Concat(keyArray);

    if (groups.TryGetValue(key, out var list))
      list.Add(word);
    else
      groups.Add(key, new List<string>() { word});
  }

  foreach (var pair in groups) {
    if (pair.Value.Count > 1) {
      string[] result = new string[pair.Value.Count];

      for (int i = 0; i < pair.Value.Count;   i)
        result[i] = pair.Value[i];

      yield return result;
    }
  }
}

Detect anagrams:

public string[] FindAnagrams_Detects_Anagrams(string word, string[] candidates) {
  if (word == null || candidates == null)
    return new string[0];

  char[] keyArray = word.ToCharArray();

  Array.Sort(keyArray);

  string key = string.Concat(keyArray);

  List<string> list = new List<string>();

  foreach (string w in candidates) {
    char[] wArray = w.ToCharArray();

    Array.Sort(wArray);

    string wKey = string.Concat(wArray);
    
    if (string.Equals(wKey, key, StringComparison.OrdinalIgnoreCase)) 
      list.Add(w);
  }

  string[] result = new string[list.Count];

  for (int i = 0; i < list.Count;   i)
    result[i] = list[i];

  return result;
}
  • Related