c#查找候选字符串数组中的字符

Question

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

现在到目前为止，我在弄清楚如何收集candidates中与word匹配的字谜并返回它时遇到了问题。

下面是我的代码:

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循环还是其他什么?

顺便说一下，我是如何处理我的类构造函数的，这是我第一次尝试使用它，最后我认为我没有正确地调用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;
}