-1
我正在做以下任務(在C#中):我們有一組字母和一個英文字典。根據提供的字母查找所有可能的單詞組合。爲此,我使用trie數據結構 - 我從剩餘的字母中搜索單詞和所有可能的附加單詞(遞歸操作)。但是,該操作非常耗費時間/空間。任何想法如何更有效地處理它?Trie - 查找所有可能的句子
編輯 這是示例代碼我準備:
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;
}
}
你能否提供一些示例代碼來告訴我們你目前有什麼? – kevin 2015-01-31 17:58:42
你應該發佈你的代碼或至少解釋你使用的算法更清楚一點。我們不知道爲什麼手術需要時間/空間,直到我們瞭解您如何執行手術。 – Jacob 2015-01-31 17:58:45
另外,你提到空間消耗;你能告訴我們你是如何存儲trie的嗎? – Jacob 2015-01-31 18:08:33