algoadvance

Leetcode 720. Longest Word in Dictionary

Problem Statement

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.

Clarifying Questions

  1. Input Constraints:
    • Are there any constraints on the length of the individual words in words?
    • Is it safe to assume that all strings contain only lowercase English letters?
  2. Output Specifics:
    • If there are multiple longest words, should the function always return the lexicographically smallest one?
  3. Edge Cases:
    • What if words is empty?
    • What if no word can be built incrementally from other words?

Assuming the words array won’t be too large and we can handle it within typical memory and computation time constraints.

Strategy

  1. Data Structures:
    • Use a set<string> to efficiently check if a prefix exists.
    • Maintain a variable to track the longest valid word found.
  2. Sorting:
    • Sort the words array:
      • First by length (ascending order).
      • Second lexicographically to handle ties by default.
  3. Building the Result:
    • Iterate through each word in the sorted list.
    • For each word, check if all prefixes (one character shorter forms) of the word exist in the set.
    • If they do, update the longest word variable.

Code

Here is the C++ code implementing the above strategy:

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>

using namespace std;

string longestWord(vector<string>& words) {
    // Sort words by length and lexicographically
    sort(words.begin(), words.end(), [](const string &a, const string &b) {
        return a.length() == b.length() ? a < b : a.length() < b.length();
    });
    
    set<string> built;
    string longest = "";
    
    for (const string &word : words) {
        if (word.length() == 1 || built.find(word.substr(0, word.length() - 1)) != built.end()) {
            built.insert(word);
            if (word.length() > longest.length()) {
                longest = word;
            }
        }
    }
    
    return longest;
}

int main() {
    vector<string> words = {"w","wo","wor","worl","world"};
    cout << longestWord(words) << endl;  // Expected output: "world"
    return 0;
}

Time Complexity

Thus, the overall time complexity is (O(n \log n)).

The space complexity is (O(n)) for storing the words in the set.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI