NUHMAN.com

Introduction

LeetCode 140: Word Break II extends the classic Word Break problem by not only checking if a string can be segmented, but also asking us to return all possible segmentations using the dictionary words. This makes the problem more complex, requiring backtracking with memoization for efficiency.

Problem Statement

Given a string s and a list of strings wordDict, return all possible sentences you can form by inserting spaces into s such that every word is in wordDict.

You may return the answers in any order.

Example

go

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

Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: [
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
go

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []

Approach

We use DFS (Backtracking) with memoization to avoid recomputing results for the same substring.

✅ Steps:

1. Use a map (memo) to cache results for each substring.
2. For each prefix of s, check if it exists in the dictionary.
3. Recursively solve for the suffix and concatenate the results.
4. Return all possible combinations.

Go Implementation

go

package main

import (
    "fmt"
    "strings"
)

func wordBreak(s string, wordDict []string) []string {
    wordSet := make(map[string]bool)
    for _, word := range wordDict {
        wordSet[word] = true
    }

    memo := make(map[string][]string)

    var dfs func(string) []string
    dfs = func(sub string) []string {
        if val, ok := memo[sub]; ok {
            return val
        }

        var res []string

        if wordSet[sub] {
            res = append(res, sub)
        }

        for i := 1; i < len(sub); i++ {
            prefix := sub[:i]
            if wordSet[prefix] {
                suffix := sub[i:]
                suffixBreaks := dfs(suffix)
                for _, sentence := range suffixBreaks {
                    res = append(res, prefix+" "+sentence)
                }
            }
        }

        memo[sub] = res
        return res
    }

    return dfs(s)
}

Time and Space Complexity

MetricComplexityTime ComplexityO(2^n) worst caseSpace ComplexityO(n·k) with memoization

• Without memoization, the time complexity would be exponential.
• With memoization, we avoid recomputation, making it feasible for medium-size inputs.

Why This Works

• The backtracking explores all possible partitions.
• Memoization ensures we don’t recompute the same substring multiple times.
• The word set ensures O(1) lookup for valid dictionary words.

Edge Cases

• Empty string → should return an empty array.
• No valid combinations → return an empty list.
• Entire string is a valid word → should include that in the results.

Conclusion

LeetCode 140: Word Break II is an excellent example of combining backtracking with memoization. It's ideal for mastering recursive problem solving with optimization strategies in Go. This problem teaches you how to generate all combinations while keeping the performance under control with caching.