Leet Code 720. Longest Word in Dictionary

Example 1:

Input: words = ["a","banana","app","appl","ap","apply","apple"]
Output: "apple"
Explanation: Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

package pep.Day80;

public class LeetCode_720_Longest_Word_in_Dictionary {
    public static void main(String[] args) {
        String[] words = {"w", "wo", "wor", "worl", "world", "worles", "worle"};
        System.out.println(longestWord(words));
    }

    static class Node {
        Node[] children = new Node[26];
        String isEnd = null;
    }

    static Node root = new Node();

    public static void insert(String word) {
        Node curr = root;
        for (int i = 0; i < word.length(); i++) {
            char tba = word.charAt(i);
            if (curr.children[tba - 'a'] == null)
                curr.children[tba - 'a'] = new Node();
            curr = curr.children[tba - 'a'];
        }
        curr.isEnd = word;
    }

    static String ans = "";

    public static String longestWord(String[] words) {
        for (String word : words) {
            insert(word);
        }
        dfs(root);
        return ans;
    }

    private static void dfs(Node node) {
        for (Node child : node.children) {
            if (child != null && child.isEnd != null) {
                // aab check krenge ki better potential ans mil rha ho

                if (child.isEnd.length() > ans.length())
                    ans = child.isEnd;
                dfs(child);

            }
        }
    }
}