Leetcode 524: Longest Word in Dictionary through Deleting
grid47 Exploring patterns and algorithms
Sep 15, 2024
6 min read
Solution to LeetCode 524: Longest Word in Dictionary through Deleting Problem
Given a string s and a string array dictionary, return the longest string from the dictionary that can be formed by deleting some characters of s. If there are multiple valid words, return the longest word with the smallest lexicographical order. If no valid word exists, return an empty string.
Problem
Approach
Steps
Complexity
Input: The input consists of a string s and an array of strings dictionary.
Example: s = 'xyzzabca', dictionary = ['abc', 'xy', 'zz', 'xyz']
Constraints:
• 1 <= s.length <= 1000
• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 1000
• s and dictionary[i] consist of lowercase English letters.
Output: Return the longest word in the dictionary that can be formed from the string s. If there are multiple such words, return the lexicographically smallest one. If no valid word can be formed, return an empty string.
Example: 'abc', 'c'
Constraints:
• The output should be a string.
Goal: The goal is to check each word in the dictionary to see if it can be formed by deleting characters from s and then return the longest, lexicographically smallest one.
Steps:
• 1. Iterate through each word in the dictionary.
• 2. For each word, check if it can be formed by deleting some characters from s by maintaining a pointer for both strings.
• 3. Track the longest valid word found and update if a new word with a longer length or smaller lexicographical order is found.
• 4. Return the valid word or an empty string if no valid word is found.
Goal: The constraints on the input string s and the dictionary ensure that the solution must be efficient enough to handle large inputs.
Steps:
• 1 <= s.length <= 1000
• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 1000
• s and dictionary[i] consist of lowercase English letters.
Assumptions:
• The input strings are valid and consist of lowercase English letters only.
• We assume that all words in the dictionary are distinct.
• Explanation: The word 'abc' can be formed from s by deleting 'x', 'y', 'z', and 'z'. The other words cannot be formed.
• Input: s = 'abc', dictionary = ['a', 'b', 'c']
• Explanation: 'c' is the longest valid word that can be formed from s.
• Input: s = 'abcxyz', dictionary = ['ax', 'bc', 'xyz']
• Explanation: 'ax' can be formed from s and is the longest, lexicographically smallest word.
Approach: The approach involves iterating over each word in the dictionary and checking if it can be formed from s by deleting characters. The key operation is maintaining a pointer for both the string and the word being checked.
Observations:
• The task is a typical string matching problem where we are allowed to delete characters from s.
• The solution needs to efficiently check if a word can be formed from s and track the longest, lexicographically smallest result.
Steps:
• 1. Sort the dictionary in lexicographical order to ensure we can always pick the smallest word first.
• 2. For each word, check if it can be formed by traversing s and matching the characters of the word in sequence.
• 3. Track the longest word found, and if two words are of the same length, return the lexicographically smallest one.
Empty Inputs:
• Handle empty string s or an empty dictionary.
Large Inputs:
• The solution should efficiently handle the case where s and the dictionary contain the maximum number of elements (1000).
Special Values:
• If no word can be formed, return an empty string.
Constraints:
• The solution should run in O(n * m) time, where n is the length of s and m is the total length of all words in the dictionary.
string findLongestWord(string s, vector<string>& d) {
string ans;
for(int i =0; i < d.size(); i++) {
int pi =0, pj =0;
for(; pi < s.size() && pj < d[i].size(); pi++) {
pj += s[pi] == d[i][pj];
}
if(pj == d[i].size() && (ans.size() < d[i].size() || (ans.size() == d[i].size() && ans > d[i])))
ans = d[i];
}
return ans;
}
Defines the function `findLongestWord` that takes a string `s` and a vector of strings `d`, and returns the longest word from `d` that can be formed by deleting some characters from `s`.
2 : Variable Initialization
string ans;
Initializes the variable `ans` to store the result, which will be the longest word found from the dictionary `d`.
3 : Looping through Dictionary
for(int i =0; i < d.size(); i++) {
Starts a loop to iterate through each word in the dictionary `d`.
4 : Variable Initialization
int pi =0, pj =0;
Initializes two variables `pi` and `pj`, which represent the current indices in the string `s` and the current word `d[i]` being checked, respectively.
5 : Matching Loop
for(; pi < s.size() && pj < d[i].size(); pi++) {
Starts a loop to iterate through the string `s` and the current word `d[i]` simultaneously. It continues as long as both indices are within the bounds of `s` and `d[i]`.
6 : Character Matching
pj += s[pi] == d[i][pj];
Increments the index `pj` if the characters `s[pi]` and `d[i][pj]` match. This helps in checking if `d[i]` is a subsequence of `s`.
7 : Subsequence Validity and Lexicographical Check
Checks if `d[i]` is a subsequence of `s` (i.e., if `pj` equals the length of `d[i]`), and if it is, compares it with the current longest word `ans` to ensure that the longest and lexicographically largest word is selected.
8 : Assign Longest Word
ans = d[i];
If the current word `d[i]` is a valid subsequence and is either longer or lexicographically larger than `ans`, it updates `ans` with `d[i]`.
9 : Return Result
return ans;
Returns the longest word found from `d` that can be formed by deleting characters from `s`.
Best Case: O(n * m), where n is the length of s and m is the total length of all dictionary words.
Average Case: O(n * m)
Worst Case: O(n * m)
Description: In the worst case, we check every word in the dictionary against the entire string s.
Best Case: O(1), if no valid word is found.
Worst Case: O(m), where m is the total length of all words in the dictionary.
Description: Space complexity is determined by the dictionary size and the string s, with no extra space used apart from variables for tracking results.
