We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Word in Dictionary through Deleting

Difficulty: Medium

Problem Description

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

Key Insights

  • The goal is to find the longest word in the dictionary that can be formed by deleting characters from the string s.
  • A word can be formed if all its characters appear in s in the same order, but not necessarily consecutively.
  • If multiple words have the same length, the lexicographically smaller one should be chosen.
  • The problem can be approached using a two-pointer technique to verify if a word can be formed from s.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of s and m is the average length of the words in dictionary.
Space Complexity: O(1), since we are only using a constant amount of extra space.

Solution

To solve this problem, we can use the two-pointer technique to check if each word in the dictionary can be formed from s. For each word, we will iterate through s while checking if we can match the characters of the word in order. We will keep track of the longest valid word and update it accordingly. Sorting the dictionary helps ensure that we can easily find the lexicographically smallest word in case of ties.

Code Solutions

def findLongestWord(s: str, dictionary: List[str]) -> str:
    # Sort the dictionary to ensure lexicographical order
    dictionary.sort()
    longest_word = ""
    
    for word in dictionary:
        if len(word) > len(longest_word) and canForm(word, s):
            longest_word = word
    return longest_word

def canForm(word: str, s: str) -> bool:
    # Two pointers to check if word can be formed from s
    i, j = 0, 0
    while i < len(word) and j < len(s):
        if word[i] == s[j]:
            i += 1
        j += 1
    return i == len(word)
← Back to All Questions