如何在TRIE中找到最长的弦

Question

我已经用两个类实现了一个DS Trie:Trie和TrieNode。我需要编写一个函数，返回在O(h)中Trie中最长的字符串。我的TrieNode有一个字段LinkedList，它存储每个节点的子节点。我们还没有了解到BFS或DFS，所以我正在努力思考一些创造性的方法来解决它。

我已经有了一个函数（一个单独的函数），它通过给定的char插入/创建一个新节点：在构建trie时：创建一个节点，该节点的字段'maxdepth=0'指示我当前的深度。对于我创建的每个新节点，我将一直迭代到他的父节点（每个节点已经有一个指向他的父节点的指针），依此类推，直到我到达根节点，并将他的父节点的深度增加1。现在我将创建返回最长字符串的函数：对于每个节点：遍历我的子节点，查找最大整数'max depth‘而不是向下。这样做，直到您达到'maxdepth==0'。例如，我的算法可以很好地处理这个字符串：“AACGACE”

       root      
       / \
   (2)a   g(0)     
     / 
 (1)c        
   / 
(0)e     

=>ACE实际上是最长的。但对这个字符串不起作用：“Aacgae”

      root      
      /  \
   (2)a   g(0)     
    /  \
 (0)c  (0)e      

一般来说，我试图利用创建Trie的第一个函数（运行时间:O(H*C))，因此第二个函数（返回最长字符串）的运行时间将会更少。O(h)

Answer 1

不确定你真正想做什么，但你可以在这里找到一个trie的例子。

基本上，我通过一个建设者来创建trie；让我们来简单介绍一下如何将一个单词添加到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);
}

null

现在，如果我们添加“麻烦”，将在“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”参数传递的。

null

null