Longest Valid Word with All Prefixes

Problem

Given an array of strings words[], find the longest string such that every prefix of it is also present in words[]. If multiple strings have the same maximum length, return the lexicographically smallest one. (link)

If no such string is found, return an empty string.

Examples:

Input: words[] = ["p", "pr", "pro", "probl", "problem", "pros", "process", "processor"]
Output: "pros" 
Explanation: "pros" is the longest word with all prefixes ("p", "pr", "pro", "pros") present.

Input: words[] = ["geeks", "gfg", "geeksforgeeks"]
Output: ""
Explanation: No valid strings for all their prefixes present in the words array.

**Constraints:
**1 <= words.size <= 1000
1 <= words[i].size <= 100

Solution

To solve this problem, we use tries. First, we insert all the words into the trie. Then, we check each word to see if all its prefixes exist in the trie and keep track of the longest one. If there are multiple strings with the same length, we store the smallest one in lexicographical order.

Time - O(n x y) y is avg word length

Space - O(n x y)

class Solution {

    class Node {
        boolean flag;
        Node[] nodeArr;

        Node(){
            this.nodeArr = new Node[26];
            flag = false;
        }

        public boolean containsKey(char chr){
            return nodeArr[indexOf(chr)] != null;
        }

        public void put(char chr, Node node){
            nodeArr[indexOf(chr)] = node;
        }

        public Node next(char chr){
            return nodeArr[indexOf(chr)];
        }

        public void setEnd(){
            this.flag = true;
        }
        public boolean isEnd(){
            return this.flag;
        }
        private int indexOf(char chr){
            return chr - 'a';
        }
    }

    class Trie {
        Node root;

        Trie() {
            root = new Node();
        }

        public void insert(String word){
            Node node = root;

            for(int i=0; i<word.length(); i++){
                char chr = word.charAt(i);
                if(!node.containsKey(chr)){
                    node.put(chr, new Node());
                }
                node = node.next(chr);
            }

            node.setEnd();
        }

        public boolean search(String word){
            Node node = root;

            for(int i=0; i<word.length(); i++){
                char chr = word.charAt(i);
                if(!node.containsKey(chr)){
                    return false;
                }
                node = node.next(chr);
            }

            return node.isEnd();
        }
    }

    public String longestValidWord(String[] words) {
        Trie trie = new Trie();

        for(int i=0; i<words.length; i++){
            trie.insert(words[i]);
        }

        String ansWord = "";

        for(int i=0; i < words.length; i++){
            String text = "";
            String word = words[i];
            for(int j=0; j<word.length(); j++){
                text += word.charAt(j);
                if(!trie.search(text)){
                    break;
                }

                if(text.length() == word.length())
                    ansWord = maxWord(ansWord, word);
                }
            }
            return ansWord;
        }

        private String maxWord(String ansWord, String word){

            if(ansWord.length() < word.length()){
                return word;
            }

            if(ansWord.length() == word.length()
                && ansWord.compareTo(word) > 0){
                return word;
            }

            return ansWord;
        }
}