C# 从候选字符串数组中查找变位词

Question

我的任务是实现一种可以 return 正确的字谜子列表的方法。

到目前为止，我在弄清楚如何收集 candidates 中匹配 word 和 return 的字谜时遇到问题。

这是我现在的代码：

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

我应该在 if 语句中做第二个 for 循环还是其他。

顺便说一句，我是如何使用我的 class 构造函数的，这是我第一次尝试使用它，最后我认为我没有调用 sourceWord 变量正确..

这是我稍后需要通过的测试场景之一：

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

很遗憾，无法在此任务上使用 LINQ。

Answer 1

如果两个词是变位词，则它们具有相同个相同个字母：

 art ~ rat ~ tar

我们可以对每个单词中的字母进行排序，并通过这些键对单词进行分组：

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

代码：

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

演示：

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

结果：

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

编辑： 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(); 
  }

如果需要，您可以摆脱 Linq：

所有字谜：

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

检测字谜：

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

C# 从候选字符串数组中查找变位词

C# find anagram from a string array of candidates

c#

arrays

constructor

for-loop

anagram