将现有的字符一起匹配成单词并检查单词是否出现在给定的单词列表中?

Question

我有一个这样的单词列表:

string[] listWords = "la,lam,lan,son,som,some,mos,mao,sehi,noesrh,nroeh,doise".Split(',');

上面的列表词是字符的组合，它们都有意义。我们可以暂时称它为字典。

接下来，我有一个字符数组的多个列表，像这样:

string[] charArr1 = "a,j,s".Split(',');
string[] charArr2 = "c,l,o".Split(',');
string[] charArr3 = "d,m,n".Split(',');
string[] charArr4 = "n,e,w".Split(',');
string[] charArr5 = "f,o,x".Split(',');
string[] charArr6 = "h,q,z".Split(',');
string[] charArr7 = "i,r".Split(',');

我想把字符连接在一起。对于每个charArray，我将取出1个字符并将它们连接在一起成为单词，然后我将检查这些连接的单词是否在listwords[]列表中。如果存在，我将把单词保存在saveWords[]数组中。条件:

• 相同charArray[]的字符不连接在一起，每个charArray[]每次只能选择一个字符。
• 匹配所有大小写，不遗漏任何大小写。

,

• a + c→ac(正确匹配)->在listwords中搜索[]->不显示
• a+j(匹配不当)
• a+s(匹配不当)
• a + c + d→add(正确匹配)->在listwords中搜索[]->不显示
• s + e +我+ h→seih(正确匹配)->在listwords中搜索[]->不显示
• s + e + h + i→sehi(正确匹配)->在listwords中搜索[]->如果这个单词出现->保存到saveWords[] array

我的意思是字符的连接不会错过任何大小写。如:

• charArr1 [] + charArr2[]→将匹配以下情况:a+c, a+l, a+o, j+c, j+l, j+o, s+c, s+l, s+o
• charArr2 [] + charArr1[]→将匹配以下情况:c+a, c+j, c+s, l+a,l+j, l+s,o+a,o+j, o+s
• charArr1 + charArr2 + charArr3
• charArr1 [] + charArr3 [] + charArr2 []
• charArr2 [] + charArr1 [] + charArr3 []
• charArr2 [] + charArr3 [] + charArr1 []

请帮助我，因为我在计算算法时感到困惑。非常感谢。

Answer 1

给定

public static IEnumerable<string[]> Permutate(string[] array, int i, int n)
{
if (i == n)
yield return array;
else
for (var j = i; j <= n; j++)
{
Swap(ref array[i], ref array[j]);
foreach (var s in Permutate(array, i + 1, n))
yield return s;
Swap(ref array[i], ref array[j]);
}
}
public static void Swap(ref string a, ref string b) => (a, b) = (b, a);
public static bool IncMask(string[][] source, int[] mask)
{
for (var i = 0; i < mask.Length; i++)
{
mask[i]++;
if (mask[i] > source[i].Length)
mask[i] = 0;
else
return false;
}
return true;
}
public static IEnumerable<string> Iterate(params string[][] source)
{
var masks = new int[source.Length];
while (true)
{
if (IncMask(source, masks))
break;
var array = masks
.Select((i, j) => (i, j))
.Where(x => x.i != 0)
.Select(x => source[x.j][x.i - 1])
.ToArray();
foreach (var result in Permutate(array, 0, array.Length - 1))
yield return string.Concat(result);
}
}

使用

var listWords = "la,lam,lan,son,som,some,mos,mao,sehi,noesrh,nroeh,doise".Split(',');
var charArr1 = "a,j,s".Split(',');
var charArr2 = "c,l,o".Split(',');
var charArr3 = "d,m,n".Split(',');
var charArr4 = "n,e,w".Split(',');
var charArr5 = "f,o,x".Split(',');
var charArr6 = "h,q,z".Split(',');
var charArr7 = "i,r".Split(',');
var results = Iterate(charArr1, charArr2, charArr3, charArr4, charArr5, charArr6, charArr7)
.Where(x => listWords.Contains(x));
Console.WriteLine(string.Join(", ", results));

结果

la, lam, mao, som, mos, lan, son, lan, son, some, mao, som, mos, son, son, some, doise, doise, sehi, nroeh, noesrh, nroeh, noesrh

注意，这是一个计算量相当大的问题，我没有花太多精力使其高效，也不关心重复。它可能有许多其他(更高效)的解决方法。此外，我只是最低限度地测试了这一点，所以我不负责任何人你致残或以其他方式伤害这个代码。这可能是完全错误的¯_(ツ)_/¯