[Leetcode] 211. Design Add and Search Words Data Structure

https://leetcode.com/problems/design-add-and-search-words-data-structure/description/?envType=study-plan-v2&envId=top-interview-150

initial

so coming back from trie, we just need to do how to deal with this search function cuz . can be equal to any character.

very impt in java
1) ascii value of . is greater than that of any alphabet so the if statement to check . MUST COME BEFORE checking any alphabet

like

if char =='.'
else

not like
*error*
if char==alphabet
else

2) if ur putting 2 conditions in if statement u MUST make sure u dont cause any exceptions like list out of range . This is cuz (i dont rly get it im not using idx or word when checking node.endOfWord so why get this stringarrayoutofbounds error?)

error

if(idx==word.length() && node.endOfWord())

correct

if(idx==word.length()) return node.endOFWord

sol

we use dfs to recursively check down for all possible paths when we meet a .

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

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


class WordDictionary {
    private Node root;
    public WordDictionary() {
        this.root = new Node();
    }
    
    public void addWord(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) {
        return dfs(root,word,0);
        
    }

    public boolean dfs(Node node, String word, int idx){
        if(idx==word.length()) return node.endOfWord;
        char c=  word.charAt(idx);
        if (c=='.'){
            for (Node check: node.children){
                if(check!=null && dfs(check,word,idx+1)) return true;
            }
            return false;
        } else {
            if (node.children[c-'a']==null) return false;
            node = node.children[c-'a'];
            return dfs(node,word,idx+1);  
        }
    }
}

complexity

insert o (l) time
search - if theres no dot it is o(l) but if theres k dots and worst case its k26l

space is number of nodes created
n*l worst case