{x}
blog image

Longest Word in Dictionary through Deleting

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.

 

Example 1:

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

Example 2:

Input: s = "abpcplea", dictionary = ["a","b","c"]
Output: "a"

 

Constraints:

  • 1 <= s.length <= 1000
  • 1 <= dictionary.length <= 1000
  • 1 <= dictionary[i].length <= 1000
  • s and dictionary[i] consist of lowercase English letters.

Solution Explanation for LeetCode 524: Longest Word in Dictionary through Deleting

This problem asks us to find the longest word in a given dictionary that can be formed by deleting some characters from a given string s. If multiple words satisfy this condition, we should choose the lexicographically smallest one.

Approach: Subsequence Check

The core idea is to efficiently check if a word from the dictionary is a subsequence of the input string s. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

We can achieve this subsequence check using a two-pointer approach:

  1. check(s, t) function: This function takes two strings, s (the input string) and t (a word from the dictionary), and determines if t is a subsequence of s. It uses two pointers, i for s and j for t. It iterates through s. If s[i] matches t[j], we increment both pointers, indicating a match. If s[i] doesn't match, we only increment j. If we reach the end of t (j == len(t)), it means all characters of t were found in s in the correct order, so t is a subsequence.

  2. Iteration and Comparison: We iterate through each word t in the dictionary. For each word, we call check(t, s) to see if it's a subsequence. If it is:

    • We compare its length with the length of the current longest word (ans). If it's longer, or if it's the same length but lexicographically smaller, we update ans.

Time and Space Complexity Analysis

  • Time Complexity: The check function takes O(m + n) time in the worst case, where m is the length of s and n is the length of t. Since we call check for each word in the dictionary (d words), the overall time complexity is O(d * (m + n)). In the worst case, n could be significantly smaller than m, but it is dependent on the input dictionary.

  • Space Complexity: The space complexity is O(1) because we are using only a constant amount of extra space to store pointers and the ans string.

Code Implementation in Multiple Languages

The provided code examples in Python, Java, C++, Go, TypeScript, and Rust all implement this approach. They all follow the same logic: a check function for subsequence verification and a main loop that iterates through the dictionary, comparing words based on length and lexicographical order. The specific syntax and library calls vary based on the programming language. The core algorithmic structure remains consistent.