140.Word_Break_II(Hard).md

140. Word Break II (Hard)

Date and Time: Jun 2, 2025

Link: https://leetcode.com/problems/word-break-ii

Walk-through:

Brute force approach with backtracking by forming word s[i:j+1], j is between i to len(s) and check if this word in wordDict (we can convert wordDict to set() beforehand). If this word in wordDict, save it into curr[] and run backtrack on the next index j+1.

Python:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        # Try to form word from index 0 to i, if we can form a word, backtrack from i+1
        # TC: O(n*2^n), n=len(s), SC: O(2^n), wether put space on each index

        ans = []
        wordDict = set(wordDict)
        def backtr(i, curr):
            if i == len(s):
                ans.append(" ".join(curr))
            for j in range(i, len(s)):
                w = s[i:j+1]
                if w in wordDict:
                    backtr(j+1, curr+[w])
        backtr(0, [])
        return ans

Time Complexity: $O(n*2^n)$
Space Complexity: $O(2^n)$, whether to put space on each index or not