Easy to understand java concise implementation with delete function (recursion implementation)


  • 0
    B

    I just add a delete function to this Trie, and did some tests. Hope it helps

    class TrieNode {
        // Initialize your data structure here.
        boolean isWord;
        TrieNode[] children;
        public TrieNode() {
            this.isWord = false;
            this.children = new TrieNode[26];
        }
        public boolean isEmpty(){
            for (int i = 0 ; i < 26 ; i++){
                if (children[i] != null){
                    return false;
                }
            }
            return true;
        }
    }
    
    public class Trie {
        private TrieNode root;
    
        public Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        public void insert(String word) {
            insertHelper(root, word, 0);
        }
        private void insertHelper(TrieNode root, String word, int index){
            if (index == word.length()){
                return;
            }
            int charIndex = word.charAt(index) - 'a';
            if (root.children[charIndex] == null){
                root.children[charIndex] = new TrieNode();
            }
            if (index == word.length() - 1){
                root.children[charIndex].isWord = true;
            }
            insertHelper(root.children[charIndex], word, index + 1);
        }
    
        // Returns if the word is in the trie.
        public boolean search(String word) {
            return searchHelper(root, word, 0);
        }
        private boolean searchHelper(TrieNode root, String word, int index){
            int charIndex = word.charAt(index) - 'a';
            if (root.children[charIndex] == null){
                return false;
            }
            if (index == word.length() - 1){
                return root.children[charIndex].isWord;
            }
            return searchHelper(root.children[charIndex], word, index + 1);
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
            return startWithHelper(root, prefix, 0);
        }
        private boolean startWithHelper(TrieNode root, String prefix, int index){
            if (index == prefix.length()){
                return true;
            }
            int charIndex = prefix.charAt(index) - 'a';
            if (root.children[charIndex] == null){
                return false;
            }
            return startWithHelper(root.children[charIndex], prefix, index + 1);
        }
        public void delete(String word){
            if (!search(word)){
                return;
            }
            deleteHelper(root, word, 0);
        }
        private void deleteHelper(TrieNode root, String word, int index){
            if (index == word.length()){
                return;
            }
            int charIndex = word.charAt(index) - 'a';
            deleteHelper(root.children[charIndex], word, index + 1);
            if (index == word.length() - 1){
                root.children[charIndex].isWord = false;
            }
            if (root.children[charIndex].isEmpty() && !root.children[charIndex].isWord){
                root.children[charIndex] = null;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.