我已经按2类实现了Trie DS Trie:Trie和TrieNode。
我需要编写一个函数，该函数返回O(h)中Trie中的最长字符串。
我的TrieNode有一个LinkedList字段，用于存储每个Node的子代。
我们仍然还没有了解BFS或DFS，因此我正在尝试考虑一些创新的方法来解决它。
我已经有了一个通过给定char插入/创建新Node的函数(一个SEPARATE函数):
构建Trie时:创建一个节点，其字段'maxDepth = 0'指示我当前的深度是多少。对于我创建的每个新节点，我将一直迭代到其父节点(每个节点都已经有一个指向其父节点的指针)，依此类推，直到到达根节点为止，并将其父节点的深度增加1。
现在，我将创建通过以下方式返回最长字符串的函数:对于每个节点:遍历我的孩子，寻找最大整数'maxDepth'而不是向下查找。直到达到“maxDepth == 0”为止。
例如，我的算法可以在以下字符串上正常工作:“aacgace”
root
/ \
(2)a g(0)
/
(1)c
/
(0)e
=>'ace'实际上是最长的。
但不适用于以下字符串:“aacgae”
root
/ \
(2)a g(0)
/ \
(0)c (0)e
=>似乎Node'a'有一个孩子，而他的孩子也有一个孩子，但这不是事实。
通常，我正在尝试利用创建Trie的第一个函数(运行时间:O(h * c))，因此，第二个函数(返回最长字符串)的运行时间将尽可能少。哦)
最佳答案
不知道您真正想要做什么，但是可以找到一个trit here的示例。
基本上，我会通过一个构建器来创建特里；让我们快速了解如何将单词添加到trie:
// In TrieBuilder
final TrieNodeBuilder nodeBuilder = new TrieNodeBuilder();
// ...
/**
* Add one word to the trie
*
* @param word the word to add
* @return this
* @throws IllegalArgumentException word is empty
*/
public TrieBuilder addWord(@Nonnull final String word)
{
Objects.requireNonNull(word);
final int length = word.length();
if (length == 0)
throw new IllegalArgumentException("a trie cannot have empty "
+ "strings (use EMPTY instead)");
nrWords++;
maxLength = Math.max(maxLength, length);
nodeBuilder.addWord(word);
return this;
}
这推迟了将单词添加到TrieNodeBuilder的功能，这样做是:
private boolean fullWord = false;
private final Map<Character, TrieNodeBuilder> subnodes
= new TreeMap<>();
TrieNodeBuilder addWord(final String word)
{
doAddWord(CharBuffer.wrap(word));
return this;
}
/**
* Add a word
*
* <p>Here also, a {@link CharBuffer} is used, which changes position as we
* progress into building the tree, character by character, node by node.
* </p>
*
* <p>If the buffer is "empty" when entering this method, it means a match
* must be recorded (see {@link #fullWord}).</p>
*
* @param buffer the buffer (never null)
*/
private void doAddWord(final CharBuffer buffer)
{
if (!buffer.hasRemaining()) {
fullWord = true;
return;
}
final char c = buffer.get();
TrieNodeBuilder builder = subnodes.get(c);
if (builder == null) {
builder = new TrieNodeBuilder();
subnodes.put(c, builder);
}
builder.doAddWord(buffer);
}
假设我们在特里添加了“麻烦”和“麻烦”。这是怎么回事:
现在，如果我们添加“麻烦”，则将在“e”之后为“s”创建另一个节点。
fullWord变量告诉我们这里是否有潜在的完全匹配项；这是搜索功能:public final class Trie
{
private final int nrWords;
private final int maxLength;
private final TrieNode node;
// ...
/**
* Search for a string into this trie
*
* @param needle the string to search
* @return the length of the match (ie, the string) or -1 if not found
*/
public int search(final String needle)
{
return node.search(needle);
}
// ...
}
在
TrieNode中，我们有:public final class TrieNode
{
private final boolean fullWord;
private final char[] nextChars;
private final TrieNode[] nextNodes;
// ...
public int search(final String needle)
{
return doSearch(CharBuffer.wrap(needle), fullWord ? 0 : -1, 0);
}
/**
* Core search method
*
* <p>This method uses a {@link CharBuffer} to perform searches, and changes
* this buffer's position as the match progresses. The two other arguments
* are the depth of the current search (ie the number of nodes visited
* since root) and the index of the last node where a match was found (ie
* the last node where {@link #fullWord} was true.</p>
*
* @param buffer the charbuffer
* @param matchedLength the last matched length (-1 if no match yet)
* @param currentLength the current length walked by the trie
* @return the length of the match found, -1 otherwise
*/
private int doSearch(final CharBuffer buffer, final int matchedLength,
final int currentLength)
{
/*
* Try and see if there is a possible match here; there is if "fullword"
* is true, in this case the next "matchedLength" argument to a possible
* child call will be the current length.
*/
final int nextLength = fullWord ? currentLength : matchedLength;
/*
* If there is nothing left in the buffer, we have a match.
*/
if (!buffer.hasRemaining())
return nextLength;
/*
* OK, there is at least one character remaining, so pick it up and see
* whether it is in the list of our children...
*/
final int index = Arrays.binarySearch(nextChars, buffer.get());
/*
* If not, we return the last good match; if yes, we call this same
* method on the matching child node with the (possibly new) matched
* length as an argument and a depth increased by 1.
*/
return index < 0
? nextLength
: nextNodes[index].doSearch(buffer, nextLength, currentLength + 1);
}
}
注意如何在
doSearch()的第一次调用中将-1作为“nextLength”参数传递。假设我们有一个上面三个单词的特里，这是搜索“tr”的调用序列，但失败了:
现在，如果我们有“麻烦”: