Как реализовать автозаполнение с использованием Tr ie с HashMap? - PullRequest
Новая
       87

Как реализовать автозаполнение с использованием Tr ie с HashMap?

1 голос
/ 11 апреля 2020

Здесь ниже код с реализацией HashMap Tr ie. Но я не уверен, как реализовать автозаполнение части. Я вижу, как люди использовали LinkedList для реализации Tr ie, но я хочу разобраться с HashMap. Любая помощь приветствуется. Я вставил приведенный ниже код для моего Tr ie.

. Есть ли способ найти префикс, затем go до конца префикса и найти его потомки и вернуть их обратно в виде строк? ? И если да, то как добиться реализации HashMap. Или я не должен даже делать это с HashMap и go для 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);
    }
}

1 Ответ

0 голосов
/ 16 апреля 2020

Я торопился найти какое-то другое решение здесь, но это интересный вопрос.

Ответ на этот вопрос -

Есть ли способ найти префикс, затем go до конца префикса и поиск его потомков и возврат их обратно в виде строк?

Да, почему нет, если у вас есть префикс ama, теперь go к вашему searchTrie методу, и когда вы закончите и выйдете из oop. затем у вас есть переменная 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

    }
...