Trie 实现 - getWords 和 getWordsWithPrefix

Question

我正在尝试学习和实现 Java 中的 Trie 数据结构。这不是我正在尝试学习和实现 trie 的家庭作业，使用数组而不是 Map。我正在寻找一种方法来获取 trie 中的所有单词，并根据前缀获取所有单词，在我的 TrieNode

实现中

下面是我的Java代码

import java.util.Arrays;

public class Solution
{
  private TrieNode root;

  public Solution()
  {
    root = new TrieNode();
  }

  public void insert(String word)
  {
    TrieNode current = root;
    for(int index = 0;index < word.length();index++)
    {
      char value = word.charAt(index);
      if(!current.containsKey(value))
      {
        current.put(value, new TrieNode()); 
      }
      current = current.get(value);
    }
    current.setEnd();
  }

  public TrieNode searchPrefix(String word)
  {
    TrieNode current = root;
    for(int index = 0;index < word.length();index++)
    {
      char value = word.charAt(index);
      if(current.containsKey(value))
      {
        current = current.get(value);
      }
      else
      {
        return null;
      } 
    }
    return current;
  }

  public boolean search(String word)
  {
    TrieNode node = searchPrefix(word);
    return node != null && node.isEnd();
  }

  public boolean startsWith(String word)
  {
    TrieNode node = searchPrefix(word);
    return node != null;
  }

  // Return [the, there, by, bye]
  public List<String> getWords(TrieNode root)
  {
     StringBuilder builder = new StringBuilder();
     List<String> words = new ArrayList<String>();
     getWords(words, root, builder);
     return words;
  }

  public void getWords(List<String> words, TrieNode root, StringBuilder builder)
 {
    if(root.isEnd())
    {
      words.add(builder.toString());
      builder.delete(0, builder.length());
    }

    for(int index = 0;index < 26;index++)
    {
       if(root.links[index] != null)
       {
          builder.append((char) (index + 97));
          getWords(words, root.links[index], builder);
       }
     }
  }

  // Return [by, bye] when prefix = by
  public List<String> getWords(String prefix)
  {
    List<String> words = new ArrayList<String>();

    if(root.isEnd())
    {

    }

    for(int index = 0;index < 26;index++)
    {

    }
    return words;
  }



  public static void main(String[] args)
  {
    Solution trie = new Solution();
    trie.insert("the");
    trie.insert("there");
    trie.insert("by");
    trie.insert("bye");

    System.out.println(trie.search("thee"));
    System.out.println(trie.search("the"));
    System.out.println(trie.startsWith("by"));
    System.out.println(trie.search("by"));
    System.out.println(trie.wordCount(trie.root));
    System.out.println(trie.getWords(trie.root));
  }
}

class TrieNode
{
  public TrieNode[] links;
  private final int R = 26;
  private boolean isEnd;

  public TrieNode()
  {
    links = new TrieNode[R];
  }

  public boolean isEnd()
  {
    return isEnd;
  }

  public void setEnd()
  {
    this.isEnd = true;
  }

  public boolean containsKey(char value)
  {
    return links[value - 'a'] != null;
  }

  public void put(char value, TrieNode node)
  {
    links[value - 'a'] = node;
  }

  public TrieNode get(char value)
  {
    return links[value - 'a'];
  }
}

我正在寻找一种方法，使 getWords 不会在最后得到过滤器 (isEnd())

 getWords => [by, e, the, re]

任何输入都会有所帮助。

谢谢！

Answer 1

不确定您到底需要哪个函数的帮助，但我快速实现了一个空函数。

// Return [by, bye] when prefix = by
public List<String> getWords(String prefix)
{
    TrieNode trieNode = searchPrefix(prefix);
    if (trieNode != null) {
        List<String> words = new ArrayList<>();
        addAllWords(trieNode, prefix, words);
        return words;
    }
    return Collections.emptyList();
}

private void addAllWords(TrieNode node, String word, List<String> words)
{
    if (node.isEnd()) {
        words.add(word);
    }
    for(int index = 0;index < 26;index++)
    {
        TrieNode next = node.get((char)(index + 'a'));
        if (next != null) {
            addAllWords(next, word + (char)(index + 'a'), words);
        }
    }
}

在 TrieNode 中添加一个 get(int index) 会稍微简化一些事情，现在 char 来回转换。

Trie 实现 - getWords 和 getWordsWithPrefix

Trie implementation - getWords and getWordsWithPrefix

java

arrays

trie