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
1class Solution {
2 public:
3 static bool comp(string s, string t) { // sorting comparator
4 return s.size() < t.size();
5 }
6 string longestWord(vector<string>& words) {
7 sort(words.begin(), words.end(), comp); // sort words by non-decreasing length
8 unordered_map<string, bool> goodWords; // lookup for good words
9 int maxLength = 0;
10 string ans = "";
11 for (string word : words) {
12 if (word.size() == 1) {
13 goodWords[word] = true;
14 } else if (goodWords[word.substr(0, word.size() - 1)]) { // word with length - 1 prefix is good
15 goodWords[word] = true;
16 }
17 if (goodWords[word]) {
18 if (maxLength < word.size()) { // find longer word
19 maxLength = word.size();
20 ans = word;
21 } else if (maxLength == word.size()) { // find lexicographically smaller word
22 ans = min(ans, word);
23 }
24 }
25 }
26 return ans;
27 }
28};
Java Solution
1class Solution {
2 public String longestWord(String[] words) {
3 Arrays.sort(words, (a, b) -> a.length() - b.length()); // sort words by non-decreasing length
4 HashMap<String, Boolean> goodWords = new HashMap(); // lookup for good words
5 int maxLength = 0;
6 String ans = "";
7 for (String word : words) {
8 if (word.length() == 1) {
9 goodWords.put(word, true);
10 } else if (goodWords.containsKey(word.substring(0, word.length() - 1))) {
11 // word with length - 1 prefix is good
12 goodWords.put(word, true);
13 }
14 if (goodWords.containsKey(word)) {
15 if (maxLength < word.length()) { // find longer word
16 maxLength = word.length();
17 ans = word;
18 } else if (maxLength == word.length()
19 && ans.compareTo(word) > 0) { // find lexicographically smaller word
20 ans = word;
21 }
22 }
23 }
24 return ans;
25 }
26}
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.
1class Solution: 2 def longestWord(self, words: List[str]) -> str: 3 words.sort(key=len) # sort words by non-decreasing length 4 goodWords = set() # lookup for good words 5 maxLength = 0 6 ans = "" 7 for word in words: 8 if len(word) == 1: 9 goodWords.add(word) 10 elif word[:-1] in goodWords: # word with length - 1 prefix is good 11 goodWords.add(word) 12 if word in goodWords: 13 if maxLength < len(word): # find longer word 14 maxLength = len(word) 15 ans = word 16 elif maxLength == len(word): # find lexicographically smaller word 17 ans = min(ans, word) 18 return ans 19
Which of the following is a min heap?
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Solution Implementation
Depth first search can be used to find whether two components in a graph are connected.
Is the following code DFS or BFS?
1void search(Node root) { 2 if (!root) return; 3 visit(root); 4 root.visited = true; 5 for (Node node in root.adjacent) { 6 if (!node.visited) { 7 search(node); 8 } 9 } 10}
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
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
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.