[Leetcode] 208. Implement Trie (Prefix Tree)

https://leetcode.com/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-interview-150

initial

so using a hashmap is out of question cuz of time complexity like for search we have to search every word

we have to use our own Node class that has 2 attributes - array of size 26 alphabets with type Node and a boolean endOfWord

Rmb that when u init array, the elements are all null

sol

impt thing is that we move the pointer to its children whenever we search or insert. Like pointer should be at first from root and go to the next alphabet and so on.

like root -> c -> a -> t

class Node{
    public boolean endOfWord;
    public Node[] children; 

    public Node(){
        this.endOfWord=false;
        this.children = new Node[26];
    }
}

class Trie {
    private Node root;

    public Trie() {
        this.root=new Node();
    }
    
    public void insert(String word) {
        Node curNode = root;
        for(char c: word.toCharArray()){
            if (curNode.children[c-'a']==null){
                curNode.children[c-'a']=new Node();
            }
            curNode=curNode.children[c-'a'];
        }
        curNode.endOfWord=true;
    }
    
    public boolean search(String word) {
        Node curNode = root;
        for(char c:word.toCharArray()){
            if (curNode.children[c-'a']==null) return false;
            curNode=curNode.children[c-'a'];
        }
        if (curNode.endOfWord) return true;
        return false;
    }
    
    public boolean startsWith(String prefix) {
        Node curNode = root;
        for(char c:prefix.toCharArray()){
            if (curNode.children[c-'a']==null) return false;
            curNode=curNode.children[c-'a'];
        }
        return true;
    }
}

complexity

insert - time is length l of word
search - time is o(l) as well
startswith - time o(l) worse case

space is no of nodes that we need to create for each word
worst case is that words do not share any prefixes so (w *l) is space