Longest Word In Dictionary - Leetcode Solution

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. 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 1: Input: s = "abpcleef" dictionary = ["ale","apple","monkey","plea"] Output: "apple"

Example 2: Input: s = "abpcleef" dictionary = ["a","b","c"] Output: ""

Solution:

The problem can be solved by sorting the dictionary array and then iterating through each word in it. For each word in the dictionary, we can check if it can be formed by deleting some characters from the input string s.

We can use two pointers technique to check if a word can be formed by deleting some characters from s. We can iterate through both the strings using two pointers i and j. If the current character of the dictionary word matches with the current character of s, we can increment both the pointers. Otherwise, we can increment only the pointer of s. If we are able to reach the end of the dictionary word, that means we can form the word by deleting some characters from s.

During the iteration, we can maintain the longest word that we have found so far. In case of multiple words with the same length, we should return the lexicographically smallest word. Therefore, we should compare the current word with the longest word found so far, and update the longest word if the current word is longer. If the current word has the same length as the longest word found so far, we should compare both the words lexicographically and update the longest word if the current word is smaller.

If we have iterated through the entire dictionary array and have not found any word that can be formed by deleting some characters from s, we should return the empty string.

The time complexity of the solution is O(N * K * logN), where N is the length of dictionary and K is the maximum length of a word in the dictionary. The space complexity of the solution is O(1).

Here is the Python code that implements the above solution:

class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        dictionary.sort()
        longest_word = ""
        for word in dictionary:
            i, j = 0, 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

1