时间戳

首页 > 解决方案 > 如何使用带有 HashMap 的 Trie 实现自动完成？

java - 如何使用带有 HashMap 的 Trie 实现自动完成？

问题描述

下面是 Trie 的 HashMap 实现的代码。但我不确定如何实现自动完成部分。我看到人们如何使用 LinkedList 来实现 Trie，但我想用 HashMap 来理解。任何帮助表示赞赏。我已经为我的 Trie 粘贴了下面的代码。

有没有办法查找前缀，然后转到前缀的末尾并查找其子项并将它们作为字符串返回？如果是这样，如何实现使用 HashMap 实现。或者我什至不应该使用 HashMap 来执行此操作并使用 LinkedList。我不确定，为什么一个比另一个好？

public class TrieNode {

    Map<Character, TrieNode> children;
    boolean isEndOfWord;

    public TrieNode() {
        isEndOfWord = false;
        children = new HashMap<>();
    }

}

public class TrieImpl {

    private TrieNode root;

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

    // iterative insertion into Trie Data Structure
    public void insert(String word) {
        if (searchTrie(word))
            return;

        TrieNode current = root;
        for(int i=0; i<word.length(); i++) {
            char ch = word.charAt(i);
            TrieNode node = current.children.get(ch);
            if(node == null) {
                node = new TrieNode();
                current.children.put(ch, node);
            }
            current = node;
        }
        current.isEndOfWord = true;
    }

    // search iteratively
    public boolean searchTrie(String word) {
        TrieNode current = root;
        for(int i=0; i < word.length(); i++) {
            char ch = word.charAt(i);
            TrieNode node = current.children.get(ch);
            if(node == null) {
                return false;
            }
            current = node;
        }
        return current.isEndOfWord;
    }


    // delete a word recursively
    private boolean deleteRecursive(TrieNode current, String word, int index) {

        if(index == word.length()) {
            if(!current.isEndOfWord) {
                return false;
            }
            current.isEndOfWord = false;
            return current.children.size() == 0;
        }
        char ch = word.charAt(index);
        TrieNode node = current.children.get(ch);

        if(node == null) {
            return false;
        }

        boolean shouldDeleteCurrentNode = deleteRecursive(node, word, index+1);

        if(shouldDeleteCurrentNode) {
            current.children.remove(ch);
            return current.children.size() == 0;
        }

        return false;
    }

    // calling the deleteRecursively function
    public boolean deleteRecursive(String word) {
        return deleteRecursive(root, word, 0);
    }

    public static void main(String[] args) {

        TrieImpl obj = new TrieImpl();

        obj.insert("amazon");
        obj.insert("amazon prime");
        obj.insert("amazing");
        obj.insert("amazing spider man");
        obj.insert("amazed");
        obj.insert("alibaba");
        obj.insert("ali express");
        obj.insert("ebay");
        obj.insert("walmart");

        boolean isExists = obj.searchTrie("amazing spider man");
        System.out.println(isExists);
    }
}

标签： javadata-structuresautocompletehashmaptrie

解决方案

我急于在这里找到其他解决方案，但这是一个有趣的问题。

回答这个——

有没有办法查找前缀，然后转到前缀的末尾并查找其子项并将它们作为字符串返回？

是的，为什么不呢，如果你有前缀ama，现在去你的searchTrie方法，当你完成并退出循环。然后，您有current指向a（最后一个字符ama）的变量

然后您可以编写如下方法 -

    public List<String> getPrefixStrings(TrieNode current){
           // DO DFS here and put all character with isEndOfWord = true in the list
           // keep on recursing to this same method and adding to the list
           // then return the list

    }

推荐阅读