algoadvance

Leetcode 524. Longest Word in Dictionary through Deleting

Problem Statement

Given a string s and a string array dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string s. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Clarifying Questions

  1. Input Constraints:
    • What are the length constraints on s and dictionary?
    • Answer: The length of s is up to 1000, and dictionary can contain up to 1000 words.
  2. Characters in Strings:
    • Are all characters in s and dictionary lowercase English letters?
    • Answer: Yes, all characters are lowercase English letters.
  3. Multiple Valid Words:
    • If there are multiple longest words that can be formed, should we return the one that is smallest lexicographically?
    • Answer: Yes, we should return the lexicographically smallest one among the longest words.

Strategy

  1. Check Subsequence:
    • Implement a helper function to check if a word from the dictionary can be formed by deleting characters from s.
  2. Iterate Over Dictionary:
    • For each word in the dictionary, check if it can be formed from s.
    • Keep track of the longest word found that can be formed.
    • If two words have the same length, choose the lexicographically smaller one.
  3. Comparison and Update:
    • Update the result whenever a new longer or lexicographically smaller valid word is found.

Time Complexity

  1. Checking Subsequence:
    • The time complexity for checking if a word d of length m is a subsequence of s of length n is O(n).
  2. Overall Complexity:
    • If there are k words in the dictionary, the overall time complexity is O(k * n), assuming the length of words in the dictionary is generally much smaller compared to n.

Code

#include <vector>
#include <string>
#include <algorithm>

bool isSubsequence(const std::string& s, const std::string& target) {
    int i = 0, j = 0;
    while (i < s.size() && j < target.size()) {
        if (s[i] == target[j]) {
            ++j;
        }
        ++i;
    }
    return j == target.size();
}

std::string findLongestWord(std::string s, std::vector<std::string>& dictionary) {
    std::string result;
    for (const std::string& word : dictionary) {
        if (isSubsequence(s, word)) {
            if (word.length() > result.length() || 
                (word.length() == result.length() && word < result)) {
                result = word;
            }
        }
    }
    return result;
}

Explanation

This approach ensures that we efficiently find the longest word from the dictionary that can be constructed by deleting some characters from s, meeting the constraints and requirements provided.

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