Java Solution using arrays


  • 0
    M
    class TrieNode {
    
    TrieNode[] backingArray;
    
    // Initialize your data structure here.
    public TrieNode() {
        backingArray = new TrieNode[27];
    }
    

    }

    public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }
    
    // Inserts a word into the trie.
    public void insert(String word) {
        insert(root,word);
    }
    
    private void insert(TrieNode trieNode, String word){
        if(word.isEmpty()){
            trieNode.backingArray[26] = new TrieNode();
            return;   
        }
        int index = word.charAt(0) - 'a';
        TrieNode next;
        if(trieNode.backingArray[index] == null){
            next = new TrieNode();
            trieNode.backingArray[index] = next;
        }else{
            next = trieNode.backingArray[index];
        }
        insert(next,word.substring(1));
    }
    
    // Returns if the word is in the trie.
    public boolean search(String word) {
        return search(root,word);
    }
    
    private boolean search(TrieNode node,String word){
        if(word.isEmpty()){
            if(node.backingArray[26] != null) return true;
            return false;
        }
        int index = word.charAt(0) - 'a';
        if(node.backingArray[index] == null) return false;
        return search(node.backingArray[index],word.substring(1));
    }
    
    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        return startsWith(root,prefix);
    }
    
    private boolean startsWith(TrieNode node, String prefix){
        if(prefix.isEmpty()) return true;
        int index = prefix.charAt(0) - 'a';
        if(node.backingArray[index] == null) return false;
        return startsWith(node.backingArray[index],prefix.substring(1));
    }
    

    }


Log in to reply
 

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