LeetCode 1858: Longest Word With All Prefixes Solution

Master LeetCode problem 1858 (Longest Word With All Prefixes), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1858. Longest Word With All Prefixes

Medium

Depth-First Search Trie

Problem Explanation

Explanation:

To solve this problem, we can use a trie data structure. We will insert all the words into the trie and then perform a depth-first search to find the longest word that has all its prefixes in the given word list.

Here's the step-by-step approach:

Create a Trie data structure with insert and search operations.
Insert all the words from the given list into the trie.
Perform a depth-first search starting from the root of the trie.
At each node, check if the current node represents a word and if all its prefixes exist in the trie.
Keep track of the longest word found so far that satisfies the condition.
Return the longest word found.

Time complexity:

Building the trie: O(n * m), where n is the number of words and m is the average length of a word.
DFS traversal: O(n * m), as we need to visit each node once.
Overall time complexity: O(n * m)

Space complexity:

The space complexity of the trie data structure is O(n * m) to store all the words.

Solution Code

class TrieNode {
    String word;
    TrieNode[] children;

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

class Solution {
    public String longestWord(String[] words) {
        TrieNode root = new TrieNode();
        
        for (String word : words) {
            TrieNode curr = root;
            for (char c : word.toCharArray()) {
                if (curr.children[c - 'a'] == null) {
                    curr.children[c - 'a'] = new TrieNode();
                }
                curr = curr.children[c - 'a'];
            }
            curr.word = word;
        }
        
        String[] result = new String[]{""};
        dfs(root, result);
        
        return result[0];
    }
    
    private void dfs(TrieNode node, String[] result) {
        if (node == null || node.word == null) {
            return;
        }
        
        if (node.word.length() > result[0].length()) {
            result[0] = node.word;
        }
        
        for (TrieNode child : node.children) {
            dfs(child, result);
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1858 (Longest Word With All Prefixes)?

This page provides optimized solutions for LeetCode problem 1858 (Longest Word With All Prefixes) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1858 (Longest Word With All Prefixes)?

The time complexity for LeetCode 1858 (Longest Word With All Prefixes) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1858 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1858 in Java, C++, or Python.

Back to LeetCode Solutions