Question

1. word break ii

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

Explanation:

🆕 New Concept Discovered: Backtracking with Memoization
Explore all valid splits and save results to avoid repeating work.

Step 1: Understand the Goal

We need to segment a string \( s \) into space-separated words such that every word exists in the given wordDict. We must return all possible valid sentences.

Because we need to find all combinations, we must explore different choices at each step. If we find a prefix of \( s \) that is a valid word, we recursively solve the problem for the remaining suffix.

Step 2: Optimize with Memoization

To avoid solving the same suffix multiple times (for example, if different prefix splits lead to the same remaining suffix), we can use a hash map to store the results of suffixes we have already computed. This technique is called memoization (or top-down dynamic programming).

For a given suffix:

1. If it is already in our memoization map, return its saved list of sentences.
2. If the suffix is empty, return a list containing an empty string [""] to act as a base case for joining.
3. Iterate through all possible prefixes of the suffix. If a prefix is in wordDict, recursively solve for the remaining part.
4. Combine the prefix with each valid sentence formed by the remaining part and store the results.

Step 3: Implement the Algorithm

Here is the Python 3 implementation of this approach:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        word_set = set(wordDict)
        memo = {}

        def backtrack(suffix: str) -> List[str]:
            # If we have already computed the result for this suffix, return it
            if suffix in memo:
                return memo[suffix]

            # Base case: if the suffix is empty, return a list with an empty string
            if not suffix:
                return [""]

            results = []

            # Try every possible split point for the current suffix
            for i in range(1, len(suffix) + 1):
                prefix = suffix[:i]
                if prefix in word_set:
                    # Recursively get all valid sentences for the remaining substring
                    sub_sentences = backtrack(suffix[i:])
                    for sub in sub_sentences:
                        if sub:
                            results.append(prefix + " " + sub)
                        else:
                            results.append(prefix)

            # Store the result in the memoization map
            memo[suffix] = results
            return results

        return backtrack(s)

Answer:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        word_set = set(wordDict)
        memo = {}

        def backtrack(suffix: str) -> List[str]:
            if suffix in memo:
                return memo[suffix]
            if not suffix:
                return [""]

            results = []
            for i in range(1, len(suffix) + 1):
                prefix = suffix[:i]
                if prefix in word_set:
                    sub_sentences = backtrack(suffix[i:])
                    for sub in sub_sentences:
                        if sub:
                            results.append(prefix + " " + sub)
                        else:
                            results.append(prefix)

            memo[suffix] = results
            return results

        return backtrack(s)