Trie - найти все возможные предложения

Question

Я выполняю следующую задачу (в C#): У нас есть группа букв и английский словарь. Найдите все возможные комбинации слов, которые создаются из предоставленных букв. Для этого я использую структуру данных trie - я ищу слова и все возможные дополнительные слова из оставшихся букв (рекурсивная операция). Тем не менее, операция занимает очень много времени/пространства. Любая идея, как справиться с этим более эффективно?

EDIT Это пример кода я подготовил:

class Trie 
    { 
     private Node root = new Node(null); 

     public void AddWord(string word) 
     { 
      root.Add(word, 0); 
     } 

     public void GetCandidates(string input) 
     { 
      var results = new List<Result>() 
      { 
       new Result() {Rest = input} 
      }; 

      Get(results); 
     } 

     private void Get(List<Result> results) 
     { 
      foreach (var result in results.Where(r => !string.IsNullOrEmpty(r.Rest)).ToList()) 
      { 
       var pattern = result.Rest.Replace(" ", string.Empty); 

       var allWords = new List<Result>(); 
       root.GetWord(string.Empty, allWords, pattern); 
       result.OhterWords = allWords; 

       Get(allWords); 
      } 


     } 
    } 

    class Node 
    { 
     protected Dictionary<char,Node> children = new Dictionary<char, Node>(); 

     public bool End { get; private set; } 

     public char? Key { get; private set; } 

     public Node(char? key) 
     { 
      Key = key; 
     } 

     public void Add(string word, int index) 
     { 
      var letter = word[index]; 
      if (!children.ContainsKey(letter)) 
      { 
       children.Add(letter, new Node(letter)); 

      } 

      var nextIndex = index + 1; 
      if (nextIndex < word.Length) 
      { 
       children[letter].Add(word, nextIndex); 
      } 
      else 
      { 
       children[letter].End = true; 
      } 
     } 

     public virtual void GetWord(string current, List<Result> allWords, string availableLetters) 
     { 
      var newCurrent = string.Concat(current, Key); 
      if (End) 
      { 
       var result = new Result() 
       { 
        Rest = availableLetters, 
        Word = newCurrent, 
       }; 


       if (!allWords.Contains(result)) 
       { 
        allWords.Add(result); 
       } 
      } 

      foreach (var letter in availableLetters) 
      { 
       if (children.ContainsKey(letter)) 
       { 
        var index = availableLetters.IndexOf(letter); 
        var tempAvailableString = availableLetters.Remove(index, 1); 
        children[letter].GetWord(newCurrent, allWords, tempAvailableString); 
       } 
      } 
     } 
    } 

    class Result 
    { 
     public List<Result> OhterWords { get; set; } 

     public string Word { get; set; } 

     public string Rest { get; set; } 

     public override bool Equals(object obj) 
     { 
      var r = obj as Result; 
      if (r == null) 
      { 
       return false; 
      } 

      return r.Word == Word && r.Rest == Rest; 
     } 
    } 

Answer 1

Вы можете попробовать Ахо-corasick алгоритм. Он использует trie, а также суффикс и альтернативные структуры данных trie.