Longest Valid Word with All Prefixes

Summary

Given a list of words, find the longest word that has all its prefixes as valid English words. For example, if the input is ["apple", "banana", "app", "appl"], the output should be "apple" because it's the longest word that has all its prefixes ("app" and "") as valid English words.

Detailed Explanation

To solve this problem, we can iterate through each word in the list. For each word, we check if all its prefixes are valid English words. If a prefix is not valid, we immediately move on to the next word. If a word has all its prefixes as valid English words and it's the longest so far, we update our result.

Here's a step-by-step breakdown of the solution:

Initialize an empty string result to store the longest valid word.
Iterate through each word in the input list.
For each word, iterate from its first character to its last character (inclusive).
For each prefix, check if it's a valid English word. We can do this by checking if the prefix is present in our dictionary of valid words.
If a prefix is not valid, break out of the inner loop and move on to the next word.
If a word has all its prefixes as valid English words and it's longer than our current result, update result.
Return result.

Time complexity: O(N*M), where N is the number of words in the input list and M is the maximum length of a word.

Space complexity: O(M), where M is the maximum length of a word.

Optimized Solutions

Java

View GeeksforGeeks Problem

import java.util.*;

public class Main {
    public static String longestValidWord(String[] dictionary) {
        String result = "";
        for (String word : dictionary) {
            boolean isValid = true;
            for (int i = 0; i < word.length(); i++) {
                if (!isValid(word.substring(0, i + 1))) {
                    isValid = false;
                    break;
                }
            }
            if (isValid && word.length() > result.length()) {
                result = word;
            }
        }
        return result;
    }

    public static boolean isValid(String word) {
        // implement your dictionary lookup logic here
        // for example, you can use a HashSet to store the valid words
        Set<String> dictionary = new HashSet<>(Arrays.asList(dictionary));
        return dictionary.contains(word);
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Sign in with Google

893334. Longest Valid Word with All Prefixes