Practice/Meta/Leetcode 140. Word Break II

Leetcode 140. Word Break II

CodingMust

Problem

You are given a string s and a list of words wordDict representing a dictionary. Your task is to find all possible ways to reconstruct the string s by combining words from the dictionary with spaces between them.

Each word from the dictionary can be used multiple times, and you must return a list of all valid sentence reconstructions. If no valid reconstruction exists, return an empty list.

The order of sentences in the output does not matter, but each word in a sentence must be separated by a single space.

Requirements

1. Return all possible valid segmentations of the input string
2. Each segmentation must use only words present in the dictionary
3. Words from the dictionary can be reused multiple times
4. Each sentence should have words separated by exactly one space
5. If no valid segmentation exists, return an empty list

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 strings in wordDict are unique
• Time complexity should be optimized using memoization to avoid redundant computation
• Space complexity should consider the memoization cache and recursion stack

Examples

Example 1:

` Input: s = "catsanddog", wordDict = ["cat", "cats", "and", "sand", "dog"] Output: ["cat sand dog", "cats and dog"] Explanation:

• "cat sand dog": 'cat' (0-2), 'sand' (3-6), 'dog' (7-9)
• "cats and dog": 'cats' (0-3), 'and' (4-6), 'dog' (7-9) `

Example 2:

Input: s = "pineapplepenapple", wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] Output: ["pine apple pen apple", "pine applepen apple", "pineapple pen apple"] Explanation: Multiple valid ways to segment using different word combinations.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] Output: [] Explanation: No valid segmentation exists because 'sandog' cannot be formed from dictionary words.