c# - 给定字典，找到包含特定字符集和字符串的所有可能单词的最佳方法是什么

Question

我正在写一个文字游戏。我可以访问字典对象来验证单词。我需要找到包含一个单词和一组附加字符的所有可能单词。例如：假设单词是“MEN”，附加字符集是“WALOHTD”。我需要一种方法来查找诸如.... 1.MEND 2.WOMEN 3.MENTAL 4. 之类的词。基本上，我们正在查看所有可能包含“MEN”和任何特定附加字符的词。

我当然可以编写可以遍历整个字典到包含子词的第一个词的代码，然后检查特定字符的存在，但这不是最佳的。它需要超过一秒钟。非常感谢对最佳解决方案的任何帮助。_rey

Answer 1

问题是常规语言和搜索数据结构的混合。

仅考虑第一个方面，我们倾向于使用正则表达式。您没有说我们是否可以重复“附加字符”。如果可以的话，这[WALOTHD]*MEN[WALOTHD]*对您的情况来说很容易，而且很容易适应。

如果我们不能重复，那么我们可以[WALOTHD]{0,7}MEN[WALOTHD]{0,7}从任何违反规则的内容开始并过滤掉（“ALLOTMENT”匹配该表达式，但重复 L 和 T）。

或者我们可以尝试构建一个更复杂的正则表达式，尽管我不确定更好的表达式所带来的收益是否会超过计算它的成本。

来自搜索字典的另一面，DAWG非常节省空间，并且使查找包含子字符串的匹配项相对高效。这不是这个难题的完全匹配，因为我们需要担心很多前缀和后缀的排列。如果没有测试，我猜如果我们不能从“附加”中重复，那将是相当不错的，如果可以的话，那将是可怕的。但这只是一个猜测。GADDAG 可能很值得一看，它比 DAWG 大，但对于这种搜索可能更快（GADDAG 用于解决拼字游戏，这与您在这里遇到的问题几乎相同）。