Formatted question description: https://leetcode.ca/all/1858.html

1858. Longest Word With All Prefixes

Level

Medium

Description

Given an array of strings words, find the longest string in words such that every prefix of it is also in words.

  • For example, let words = ["a", "app", "ap"]. The string "app" has prefixes "ap" and "a", all of which are in words.

Return the string described above. If there is more than one string with the same length, return the lexicographically smallest one, and if no string exists, return "".

Example 1:

Input: words = [“k”,”ki”,”kir”,”kira”, “kiran”]

Output: “kiran”

Explanation: “kiran” has prefixes “kira”, “kir”, “ki”, and “k”, and all of them appear in words.

Example 2:

Input: words = [“a”, “banana”, “app”, “appl”, “ap”, “apply”, “apple”]

Output: “apple”

Explanation: Both “apple” and “apply” have all their prefixes in words. However, “apple” is lexicographically smaller, so we return that.

Example 3:

Input: words = [“abc”, “bc”, “ab”, “qwe”]

Output: “”

Constraints:

  • 1 <= words.length <= 10^5
  • 1 <= words[i].length <= 10^5
  • 1 <= sum(words[i].length) <= 10^5

Solution

Use a trie to store all the words. Then do depth first search on the trie. Search the nodes from left to right to make sure that the leftmost nodes (with lexicographically smallest letters) are visited first. For the words that all nodes are ends of words, update the longest word. Finally, return the longest word.

  • class Solution {
        String longestWord = "";
    
        public String longestWord(String[] words) {
            TrieNode root = new TrieNode();
            for (String word : words) {
                TrieNode node = root;
                int length = word.length();
                for (int i = 0; i < length; i++) {
                    char letter = word.charAt(i);
                    int index = letter - 'a';
                    if (node.children[index] == null)
                        node.children[index] = new TrieNode();
                    node = node.children[index];
                }
                node.wordEnd = true;
            }
            depthFirstSearch(root, new StringBuffer());
            return longestWord;
        }
    
        public void depthFirstSearch(TrieNode node, StringBuffer sb) {
            if (node.wordEnd && sb.length() > longestWord.length())
                longestWord = sb.toString();
            for (int i = 0; i < 26; i++) {
                TrieNode child = node.children[i];
                if (child != null && child.wordEnd) {
                    sb.append((char) ('a' + i));
                    depthFirstSearch(child, sb);
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
        }
    }
    
    class TrieNode {
        boolean wordEnd;
        TrieNode[] children;
    
        public TrieNode() {
            wordEnd = false;
            children = new TrieNode[26];
        }
    }
    
  • // OJ: https://leetcode.com/problems/longest-word-with-all-prefixes/
    // Time: O(NW)
    // Space: O(NW)
    struct TrieNode {
        TrieNode *next[26] = {};
        bool word = false;
    };
    class Solution {
        void addWord(TrieNode *node, string &s) {
            for (char c : s) {
                if (!node->next[c - 'a']) node->next[c - 'a'] = new TrieNode();
                node = node->next[c - 'a'];
            }
            node->word = true;
        }
        string ans, path;
        void dfs(TrieNode *node) {
            for (int i = 0; i < 26; ++i) {
                if (!node->next[i] || !node->next[i]->word) continue;
                path += 'a' + i;
                if (path.size() > ans.size()) ans = path;
                dfs(node->next[i]);
                path.pop_back();
            }
        }
    public:
        string longestWord(vector<string>& A) {
            TrieNode root;
            for (auto &s : A) addWord(&root, s);
            dfs(&root);
            return ans;
        }
    };
    
  • print("Todo!")
    

All Problems

All Solutions