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

Question

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

例如:

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

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

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

Answer 1

前提是你有合适的英文单词集，例如

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

您可以将其转换为更方便的聚合字典，key 是一个初始字符串，所有字母都在其中排序("flea" = > "aefl", "sad" => "ads" 等)。如果两个或更多单词具有相同键，则应将它们组合到一个集合中，比如一个数组:

"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"

您需要做的就是对其进行排序并仅检查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

测试

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

会回来

flea
fleas
sad
sea