从随机字符串中查找单词列表中的单词

我正在开发一个解读类型的程序，用户可以输入随机字母，程序会迭代这些字母和单词列表，以尝试找到包含单词列表中的这些部分或全部随机字母的单词。

例如：

if Input = "sasdfle"
words found in wordlist = "sad", "fleas", "flea", etc...

单词只能包含用户输入的字母，并且每个字母不能重复。我在这里发现了多个问题，可以找到字谜词，但我似乎找不到一种算法可以完成我上面所说的操作。

我不想在这里发布整个代码，但这是我遇到问题的主要部分：

前提是您有适当的英语单词集合，例如

private static HashSet<String> s_Words = new HashSet<String>() {
  "abacus",
  //...
  "flea",
  "fleas",
  //...
  "sad",
  "sea",
  // ...
  "zoom",
};

你可以把它转换成更方便的聚合词典 with key是一个初始字符串，其中所有字母都已排序（"flea" => "aefl", "sad" => "ads"ETC。）。如果两个或多个单词有same关键，他们应该是combined进入一个集合，比如说一个数组：

"ale", "lea" => "ael" : ["ale", "lea"]

您可以通过 Linq 实现这样的字典：

private static Dictionary<String, String[]> s_Dict = s_Words
  .Select(word => new {
    Key = String.Concat(word.OrderBy(c => c)),
    Value = word})
  .GroupBy(item => item.Key, item => item.Value)
  .ToDictionary(chunk => chunk.Key, chunk => chunk.ToArray());

然后给定一个字符串

String Input = "sasdfle"

你需要做的就是sort它并检查只是256 (2 ** (length + 1) == 256) 包含和排除每个字母的组合：

string source = String.Concat(Input.OrderBy(c => c)); 

// all combinations of the set with empty one excluded, see
// http://stackoverflow.com/questions/30081908/c-sharp-linq-combinatorics-all-combinations-of-a-set-without-the-empty-set/30082360#30082360  
var result = Enumerable
  .Range(1, (1 << source.Length) - 1)
  .Select(index => string.Concat(source.Where((item, idx) => ((1 << idx) & index) != 0)))
  .SelectMany(key => {
     String[] words;

     if (s_Dict.TryGetValue(key, out words))
       return words;
     else
       return new String[0]; })
  .Distinct() // some words can be built in many ways
  .OrderBy(word => word);
//.ToArray(); // if you want to represent words as array

Test

Console.Write(String.Join(Environment.NewLine, result));

将返回

flea
fleas
sad
sea