Longest Word In Dictionary Through Deleting - Leetcode Solution

Problem Statement:

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

Example:

Input: s = "abpclefsd" dictionary = ["ale","apple","monkey","plea"]

Output: "apple"

Explanation: The "apple" can be formed by deleting the characters "b", "c", "f", "s", "d" from the string "abpclefsd".

Solution:

To solve this problem, we need to iterate over the dictionary and check whether we can form a given word by deleting some characters of the given string. If we can form the given word, then we need to check whether the length of the given word is greater than the length of the previous longest word. If the length of the given word is greater than the length of the previous longest word, then we need to update the longest word. Finally, we need to return the longest word.

Here is the step-by-step approach to solve this problem:

1. Create a variable 'longest_word' and initialize it with an empty string.
2. Iterate over all the words in the dictionary.
3. For each word in the dictionary, check whether we can form the given word by deleting some characters of the given string. We can do this by keeping two pointers, one for the given string and another for the current word in the dictionary. We keep moving both pointers until we reach the end of either string. If we reach the end of the current word in the dictionary, we can form this word by deleting some characters of the given string.
4. If we can form the given word by deleting some characters of the given string, then we need to check whether the length of the current word is greater than the length of the previous longest word. If the length of the current word is greater than the length of the previous longest word, then we need to update the 'longest_word' variable with the current word.
5. If the length of the current word is equal to the length of the previous longest word, then we need to check lexicographical order. We always need to return the longest word with the smallest lexicographical order.
6. After iterating over all the words in the dictionary, return the 'longest_word' variable.

Here is the Python implementation of the above approach:

class Solution: def findLongestWord(self, s, d): longest_word = "" for word in d: i = 0 j = 0 while i < len(s) and j < len(word): if s[i] == word[j]: j += 1 i += 1 if j == len(word): if len(word) > len(longest_word): longest_word = word elif len(word) == len(longest_word) and word < longest_word: longest_word = word return longest_word

Time Complexity:

The time complexity of this approach is O(n*m), where n is the number of words in the dictionary and m is the maximum length of a word in the dictionary.

Space Complexity:

The space complexity of this approach is O(1). We are not using any extra data structure to store the intermediate results.

1