LeetCode 524: Longest Word in Dictionary through Deleting Solution in Python – A Step-by-Step Guide

What Is LeetCode 524: Longest Word in Dictionary through Deleting?

In LeetCode 524: Longest Word in Dictionary through Deleting, you’re given a string s and a list of strings dictionary, and your task is to find the longest word in dictionary that can be formed by deleting some (or no) characters from s while preserving the relative order of the remaining characters. If multiple words tie for the longest, return the lexicographically smallest. For example, with s = "abpcplea" and dictionary = ["ale", "apple", "monkey", "plea"], “apple” (length 5) is the longest valid word. This problem builds on LeetCode 392: Is Subsequence.

Problem Statement

• Input:
• s (str): Source string.
• dictionary (List[str]): List of candidate words.
• Output: String—longest word formable by deleting from s, or "" if none.
• Rules: Subsequence must match word; longest wins; if tied, lexicographically smallest.

Constraints

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

Examples

• Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
• Output: "apple"
• “apple” (length 5) is longest; “plea” (4) is shorter.
• Input: s = "abpcplea", dictionary = ["a","b","c"]
• Output: "a"
• All length 1; “a” is lexicographically smallest.
• Input: s = "abc", dictionary = ["def"]
• Output: ""
• No word formable.

Understanding the Problem: Crafting Words by Deletion

To solve LeetCode 524: Longest Word in Dictionary through Deleting in Python, we need to find the longest word in dictionary that’s a subsequence of s—meaning we can delete characters from s to match it while keeping the order. A naive approach might generate all subsequences of s, but with lengths up to 1000, that’s impractical. We’ll explore:

• Best Solution (Sorting with Subsequence Check): O(n m k) time, O(1) space (n = dictionary length, m = avg word length, k = s length)—efficient and practical.
• Alternative Solution (Brute-Force Subsequence Generation): O(2ᵏ n m) time, O(2ᵏ) space—exhaustive but slow.

Let’s dive into the best solution with a friendly breakdown!

Best Solution: Sorting with Subsequence Check

Why Sorting with Subsequence Check Wins

The sorting with subsequence check is the best for LeetCode 524 because it optimizes the search by sorting the dictionary by length and lexicographical order, then efficiently checks each word as a subsequence of s using a two-pointer method. It runs in O(n * m * k) time and O(1) space (excluding input), making it scalable. It’s like organizing your word list and quickly ticking off matches!

How It Works

Think of this as a word-matching game:

• Step 1: Sort Dictionary:
• Sort dictionary by decreasing length, then lexicographically within same lengths.
• Step 2: Subsequence Check:
• For each word, check if it’s a subsequence of s using two pointers.
• Step 3: Find Longest:
• Return first valid word (longest, lexicographically smallest due to sort).
• Why It Works:
• Sorting ensures longest valid word is checked first.
• Subsequence check is linear per word.

It’s like a word-deletion detective!

Step-by-Step Example

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

• Step 1: Sort dictionary:
• ["monkey", "apple", "plea", "ale"] (lengths: 6, 5, 4, 3).
• Step 2: Check each:
• “monkey”:
• s: abpcplea, i=0, j=0.
• m→a (no), b→o (no), …, fails.
• “apple”:
• s: abpcplea, i=0, j=0.
• a→a, b→p, p→p, c→l, l→e, e→end, matches.
• Length 5, return “apple”.
• Result: "apple".

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

• Step 1: Sort: ["a", "b", "c"] (all 1, alphabetical).
• Step 2: “a” matches (s[0]), return “a”.
• Result: "a".

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        # Step 1: Sort dictionary by length (desc) and lexicographically
        dictionary.sort(key=lambda x: (-len(x), x))

        # Step 2: Subsequence check helper
        def is_subsequence(word, s):
            i = 0
            for char in s:
                if i < len(word) and char == word[i]:
                    i += 1
            return i == len(word)

        # Step 3: Check each word
        for word in dictionary:
            if is_subsequence(word, s):
                return word

        # Step 4: No match found
        return ""

• Line 4: Sort by decreasing length, then alphabetically.
• Lines 7-12: is_subsequence:
• Two-pointer: Match word in s, return True if all match.
• Lines 15-17: Check each word; return first match (longest, smallest).
• Line 20: Default to empty string if no match.
• Time Complexity: O(n m k)—n words, m avg word length, k = s length.
• Space Complexity: O(1)—no extra space beyond input.

It’s like a word-matching maestro!

Alternative Solution: Brute-Force Subsequence Generation

Why an Alternative Approach?

The brute-force subsequence generation solution generates all subsequences of s and checks them against the dictionary to find the longest match. It’s O(2ᵏ * n * m) time and O(2ᵏ) space—exhaustive but impractical for large strings, though it shows the full process. Great for learning subsequences!

How It Works

Picture this as a subsequence scavenger hunt:

• Step 1: Generate all subsequences of s.
• Step 2: Check each against dictionary, track longest match.
• Step 3: Return longest, lexicographically smallest match.

It’s like a string treasure dig!

Step-by-Step Example

Example: s = "ab", dictionary = ["a", "b"]

• Step 1: Subsequences of “ab”: “”, “a”, “b”, “ab”.
• Step 2: Check dictionary:
• “a” matches, length 1.
• “b” matches, length 1.
• Step 3: Longest = 1, “a” is smallest.
• Result: "a".

Code for Brute-Force Approach

Copy codeclass Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        # Step 1: Generate all subsequences
        def get_subsequences(s):
            subs = set()
            n = len(s)
            for mask in range(1 << n):
                sub = ""
                for i in range(n):
                    if mask & (1 << i):
                        sub += s[i]
                subs.add(sub)
            return subs

        # Step 2: Get subsequences and dictionary set
        subs = get_subsequences(s)
        dict_set = set(dictionary)

        # Step 3: Find longest match
        max_len = -1
        result = ""
        for sub in subs:
            if sub in dict_set:
                if len(sub) > max_len or (len(sub) == max_len and sub < result):
                    max_len = len(sub)
                    result = sub

        return result if max_len > 0 else ""

• Lines 4-12: Generate subsequences with bitmask.
• Lines 15-16: Get all subsequences and dictionary set.
• Lines 19-24: Find longest match, prefer lexicographically smaller.
• Time Complexity: O(2ᵏ n m)—exponential subsequence check.
• Space Complexity: O(2ᵏ)—store subsequences.

It’s a subsequence overachiever!

Comparing the Two Solutions

• Sorting with Check (Best):
• Pros: O(n m k), O(1), efficient.
• Cons: Subsequence logic.
• Brute-Force (Alternative):
• Pros: O(2ᵏ n m), explicit.
• Cons: Too slow for large s.

Sorting wins for practicality!

Additional Examples and Edge Cases

• ** "a", ["b"]: "".
• ** "apple", ["app", "apple"]: "apple".
• ** "xyz", ["x", "y", "z"]: "x".

Sorting handles them all!

Complexity Recap

• Sorting with Check: Time O(n m k), Space O(1).
• Brute-Force: Time O(2ᵏ n m), Space O(2ᵏ).

Sorting’s the efficiency champ!

Key Takeaways

• Sorting: Optimize search—learn at Python Basics!
• Brute Force: Full but slow.
• Strings: Subsequences are fun.
• Python: Sort and check shine!

Final Thoughts: Find That Longest Word!

LeetCode 524: Longest Word in Dictionary through Deleting in Python is a clever string challenge. Sorting with subsequence check is your fast track, while brute force shows the long way. Want more? Try LeetCode 392: Is Subsequence or LeetCode 792: Number of Matching Subsequences. Ready to delete? Head to Solve LeetCode 524 on LeetCode and craft that word today!