Untitled

// leetcode 208 ==========================================

class Trie {

    public class TrieNode {
        TrieNode children[];
        boolean isEnd;

        public TrieNode(){
            children = new TrieNode[26];
            isEnd = false;
        }
    }

    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) { // O(word.length)
        TrieNode temp = root;

        for(int i=0; i<word.length(); i++){
            char ch = word.charAt(i);
            int idx = ch - 'a';

            if(temp.children[idx] == null){
                temp.children[idx] = new TrieNode();
            }

            temp = temp.children[idx];
        }

        temp.isEnd = true;
    }
    
    public boolean search(String word) { // O(word.length)
        TrieNode temp = root;

        for(int i=0; i<word.length(); i++){
            int idx = word.charAt(i) - 'a';

            if(temp.children[idx] == null){
                return false;
            }

            temp = temp.children[idx];
        }

        return temp.isEnd;
    }
    
    public boolean startsWith(String prefix) { 
        TrieNode temp = root;

        for(int i=0; i<prefix.length(); i++){
            int idx = prefix.charAt(i) - 'a';

            if(temp.children[idx] == null){
                return false;
            }

            temp = temp.children[idx];
        }

        return true;
    }
}

// leetcode 720 ========================================== 

class Solution {
    public class TrieNode {
        TrieNode children[];
        boolean isEnd;
        String finalWord;

        public TrieNode(){
            children = new TrieNode[26];
            isEnd = false;
            finalWord = "";
        }
    }
    
    public void insert(TrieNode root, String word) { // O(word.length)
        TrieNode temp = root;

        for(int i=0; i<word.length(); i++){
            char ch = word.charAt(i);
            int idx = ch - 'a';

            if(temp.children[idx] == null){
                temp.children[idx] = new TrieNode();
            }

            temp = temp.children[idx];
        }

        temp.isEnd = true;
        temp.finalWord = word;
    }

    String ans = "";
    public void findLongest(TrieNode root){
        if(root.finalWord.length() > ans.length()){
            ans = root.finalWord;
        } else if(root.finalWord.length() == ans.length() && root.finalWord.compareTo(ans) < 0){
            ans = root.finalWord;
        }

        for(int idx = 0; idx<26; idx++){
            if(root.children[idx] != null && root.children[idx].isEnd == true){
                findLongest(root.children[idx]);
            }
        }
    }
    
    public String longestWord(String[] words) {
        TrieNode root = new TrieNode();

        for(String word: words){
            insert(root,word);
        }

        findLongest(root);
        return ans;
    }
}