Untitled
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