# Solving Leetcode Interviews in Seconds with AI: Word Break II


	# 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](https://www.chatmagic.app), 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
	```python
	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)
	```