720. Longest Word in Dictionary
Given an array of strings words
representing an English Dictionary, return the longest word in words
that can be built one character at a time by other words in words
.
If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string.
Note that the word should be built from left to right with each additional character being added to the end of a previous word.
Example 1:
Input: words = ["w","wo","wor","worl","world"]
Output: "world"
Explanation: The word "world"
can be built one character at a time by "w", "wo", "wor", and "worl"
.
Example 2:
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"
.
Constraints:
-
words.length
-
words[i].length
words[i]
consists of lowercase English letters.
Solution
Brute Force
For this problem, we're asked to find the longest word with smallest lexicographical order such that all its non-empty prefixes exist in words
. Let's call a word good if all its prefixes exist in words
. We can verify if this is the case by iterating through all prefixes to check if they all exist. Let's denote as the length of the longest good word. Out of all good words with length , we'll return the one with lexicographically least length.
Full Solution
Let's denote as the length of words[i]
.
We can observe that words[i]
is good if or the prefix of words[i]
with length is good.
Let's try to find a way to use this idea to process all words efficiently. Since processing a word with length requires a word with length to be processed, we should process words by non-decreasing length. This can be done by sorting and simply iterating through the sorted list. In addition, we'll use a hashmap to act as a lookup table for good words.
In our algorithm, we'll iterate through words by non-decreasing length. For each word, we'll check if it's good with the method mentioned above. If the word is good, we'll update it in our hashmap.
Time Complexity
Let's denote as the length of words
and as the sum of lengths of all words in words
.
Since sorting takes and our main algorithm takes from comparing keys, our final time complexity is .
Time Complexity:
Space Complexity
Since our hashmap has memory, our space complexity is .
Space Complexity:
C++ Solution
class Solution {
public:
static bool comp(string s, string t) { // sorting comparator
return s.size() < t.size();
}
string longestWord(vector<string>& words) {
sort(words.begin(), words.end(), comp); // sort words by non-decreasing length
unordered_map<string, bool> goodWords; // lookup for good words
int maxLength = 0;
string ans = "";
for (string word : words) {
if (word.size() == 1) {
goodWords[word] = true;
} else if (goodWords[word.substr(0, word.size() - 1)]) { // word with length - 1 prefix is good
goodWords[word] = true;
}
if (goodWords[word]) {
if (maxLength < word.size()) { // find longer word
maxLength = word.size();
ans = word;
} else if (maxLength == word.size()) { // find lexicographically smaller word
ans = min(ans, word);
}
}
}
return ans;
}
};
Java Solution
class Solution {
public String longestWord(String[] words) {
Arrays.sort(words, (a, b) -> a.length() - b.length()); // sort words by non-decreasing length
HashMap<String, Boolean> goodWords = new HashMap(); // lookup for good words
int maxLength = 0;
String ans = "";
for (String word : words) {
if (word.length() == 1) {
goodWords.put(word, true);
} else if (goodWords.containsKey(word.substring(0, word.length() - 1))) {
// word with length - 1 prefix is good
goodWords.put(word, true);
}
if (goodWords.containsKey(word)) {
if (maxLength < word.length()) { // find longer word
maxLength = word.length();
ans = word;
} else if (maxLength == word.length()
&& ans.compareTo(word) > 0) { // find lexicographically smaller word
ans = word;
}
}
}
return ans;
}
}
Python Solution
Note: A set can be used in python which acts as a hashset and serves the same purpose as a hashmap in this solution.
class Solution: def longestWord(self, words: List[str]) -> str: words.sort(key=len) # sort words by non-decreasing length goodWords = set() # lookup for good words maxLength = 0 ans = "" for word in words: if len(word) == 1: goodWords.add(word) elif word[:-1] in goodWords: # word with length - 1 prefix is good goodWords.add(word) if word in goodWords: if maxLength < len(word): # find longer word maxLength = len(word) ans = word elif maxLength == len(word): # find lexicographically smaller word ans = min(ans, word) return ans
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorWhat is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!