140. 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
• 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 10⁵.

Approach 01:

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& word_dict) {
        unordered_set<string> word_set{word_dict.begin(), word_dict.end()};
        unordered_map<string, vector<string>> mem;
        return wordBreak(s, word_set, mem);
    }

private:
    vector<string> wordBreak(const string& s, const unordered_set<string>& word_set, unordered_map<string, vector<string>>& mem) {
        if (const auto it = mem.find(s); it != mem.cend())
            return it->second;

        vector<string> result;

        for (int i = 1; i < s.length(); ++i) {
            const string& prefix = s.substr(0, i);
            const string& suffix = s.substr(i);
            if (word_set.count(prefix))
                for (const string& word : wordBreak(suffix, word_set, mem))
                    result.push_back(prefix + " " + word);
        }

        if (word_set.count(s))
            result.push_back(s);

        return mem[s] = result;
    }
};

from typing import *

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

        def solve(s):
            if s in memo:
                return memo[s]

            result = []
            for i in range(1, len(s)):
                prefix = s[:i]
                suffix = s[i:]
                if prefix in word_set:
                    for word in solve(suffix):
                        result.append(prefix + " " + word)

            if s in word_set:
                result.append(s)

            memo[s] = result
            return result

        return solve(s)

Time Complexity

• Recursive Exploration with Memoization:

  The recursive function wordBreak breaks down the input string s into all possible substrings to check against the word dictionary. Since the function uses memoization, each unique substring is computed only once.

• Time Complexity of the Recursion:

  Let \( n \) be the length of the string s and m be the size of the word dictionary. In the worst case, the function generates all possible substrings (of length from 1 to \( n \)) to check if they exist in the word dictionary.

  Therefore, the time complexity can be considered as \( O(n^2) \), where the substring operation takes \( O(n) \) and there are \( O(n) \) recursive calls due to the splitting at each index.

  The number of recursive calls is further reduced due to memoization, which saves results for previously computed substrings. This reduces the overall complexity but remains exponential in the worst case for highly repetitive substrings, which makes the complexity more accurately approximated as \( O(n^3) \).

• Overall Time Complexity:

  Considering the recursive calls and memoization, the overall time complexity is approximately \( O(n^3) \) in the worst case.

Space Complexity

• Space for Memoization:

  The memoization map mem stores results for each substring, which requires at most \( O(n) \) unique keys, each holding a list of strings representing different ways to split that substring. The total space needed can grow exponentially in the worst case, depending on the number of ways the substring can be split.

• Recursive Stack Space:

  The maximum depth of the recursion tree is \( O(n) \), leading to an additional space complexity of \( O(n) \) for the call stack.

• Overall Space Complexity:

  The overall space complexity is \( O(n^3) \) in the worst case due to the memoization and recursion stack.