720.Longest Word in Dictionary

1-HashSet + Brute Force

https://leetcode.com/problems/longest-word-in-dictionary/solution/

class Solution {
    public String longestWord(String[] words) {
        String ans = "";
        Set<String> set = new HashSet<>();
        for(String s : words){
            set.add(s);
        }

        for(String s : words){
            if(s.length() > ans.length() || (s.length() == ans.length() && s.compareTo(ans) < 0)){
                boolean isUpdate =  true;

                for(int i = 1; i < s.length(); i++){
                    if(set.contains(s.substring(0, i)))
                        continue;
                    else{
                        isUpdate = false;
                        break;
                    }
                }

                if(isUpdate){
                    ans = s;
                }
            }
        }
        return ans;
    }
}

2-Trie

class Solution {
    public String longestWord(String[] words) {
        Trie trie = new Trie();
        int index = 1;
        for(String s : words){
            trie.insert(s, index++);
        }
        trie.words = words;
        return trie.bfs();
    }
}

class Node { 
    char c;
    HashMap<Character, Node> children;
    int index;
    public Node(char c){
        this.c = c;
        children = new HashMap<>();
    }
}

class Trie{
    Node root;
    String[] words;
    public Trie(){
        root= new Node('0');
    }

    public void insert(String word, int index){
        Node cur = root;
        for(char c : word.toCharArray()){
            cur.children.putIfAbsent(c, new Node(c));
            cur = cur.children.get(c);
        }
        cur.index = index;
    }

    public String bfs() {
        String ans = "";
        Deque<Node> queue = new ArrayDeque<>();  
        queue.offer(root);
        while(!queue.isEmpty()){
            Node node = queue.poll();
            if(node.index > 0 || node == root){
                if(node != root){
                    String word = words[node.index - 1];
                    if(word.length() > ans.length() || word.length() == ans.length() && word.compareTo(ans) < 0){
                        ans = word;
                    }
                }
                for(Node child : node.children.values()){
                    queue.offer(child);
                }
            }
        }
        return ans;
    }
}