Introduction

In this blog post, we will explore how to solve the LeetCode problem "140" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order. Note that the same word in the dictionary may be reused multiple times in the segmentation. Example 1: Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"] Output: ["cats and dog","cat sand dog"] Example 2: Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"] Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"] Explanation: Note that you are allowed to reuse a dictionary word. Example 3: Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: [] Constraints: 1 <= s.length <= 20 1 <= wordDict.length <= 1000 1 <= wordDict[i].length <= 10 s and wordDict[i] consist of only lowercase English letters. All the strings of wordDict are unique. Input is generated in a way that the length of the answer doesn't exceed 105.

Explanation

Here's the approach:

• Dynamic Programming with Memoization: We use dynamic programming to determine if a string s[i:] can be segmented into words from wordDict. Memoization (caching) avoids redundant computations.
• Backtracking: If s[i:] is segmentable, we backtrack to construct all possible sentences. For each valid word that starts at index i, we recursively explore the remaining string.

• Optimization with Set: Convert the wordDict into a set for faster word lookup (O(1) instead of O(n)).

• Runtime Complexity: O(n^3) in the worst case due to string slicing and recursion. In practice, memoization significantly reduces the number of computations. Storage Complexity: O(n * m), where n is the length of the string s and m is the average number of sentences for each substring of s.

Code

    def wordBreak(s: str, wordDict: list[str]) -> list[str]:
    word_set = set(wordDict)
    memo = {}  # Memoization to store results for subproblems

    def word_break_helper(start_index: int) -> list[str]:
        if start_index == len(s):
            return [""]  # Base case: empty string, valid segmentation

        if start_index in memo:
            return memo[start_index]

        sentences = []
        for i in range(start_index + 1, len(s) + 1):
            word = s[start_index:i]
            if word in word_set:
                remaining_sentences = word_break_helper(i)
                for sentence in remaining_sentences:
                    if sentence:
                        sentences.append(word + " " + sentence)
                    else:
                        sentences.append(word)  # For the base case empty string

        memo[start_index] = sentences
        return sentences

    return word_break_helper(0)