Untitled

 avatar
unknown
plain_text
4 days ago
3.1 kB
2
Indexable
class Trie {
    static class Node {
        Node[] links;
        int cntEndWith;
        int cntPrefix;
        Node() {
            links = new Node[26];
            cntEndWith = 0;
            cntPrefix = 0;
        }
        boolean containsKey(char ch) {
            return links[ch - 'a'] != null;
        }
        Node get(char ch) {
            return links[ch - 'a'];
        }
        void put(char ch, Node node) {
            links[ch - 'a'] = node;
        }
        void increaseEnd() {
            cntEndWith++;
        }
        void increasePrefix() {
            cntPrefix++;
        }
        void deleteEnd() {
            cntEndWith--;
        }
        void reducePrefix() {
            cntPrefix--;
        }
    }
    private Node root;
    Trie() {
        root = new Node();
    }
    void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            if (!node.containsKey(word.charAt(i))) {
                node.put(word.charAt(i), new Node());
            }
            node = node.get(word.charAt(i));
            node.increasePrefix();
        }
        node.increaseEnd();
    }
    int countWordsEqualTo(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            if (node.containsKey(word.charAt(i))) {
                node = node.get(word.charAt(i));
            } else {
                return 0;
            }
        }
        return node.cntEndWith;
    }
    int countWordsStartingWith(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            if (node.containsKey(word.charAt(i))) {
                node = node.get(word.charAt(i));
            } else {
                return 0;
            }
        }
        return node.cntPrefix;
    }
    void erase(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            if (node.containsKey(word.charAt(i))) {
                node = node.get(word.charAt(i));
                node.reducePrefix();
            } else {
                return;
            }
        }
        node.deleteEnd();
    }
}
public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("app");
        System.out.println("Inserting strings 'apple', 'app' into Trie");
        System.out.print("Count Words Equal to 'apple': ");
        System.out.println(trie.countWordsEqualTo("apple"));
        System.out.print("Count Words Starting With 'app': ");
        System.out.println(trie.countWordsStartingWith("app"));
        System.out.println("Erasing word 'app' from trie");
        trie.erase("app");
        System.out.print("Count Words Equal to 'apple': ");
        System.out.println(trie.countWordsEqualTo("apple"));
        System.out.print("Count Words Starting With 'apple': ");
        System.out.println(trie.countWordsStartingWith("app"));
    }
}
Leave a Comment