Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
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.
Input:
- A string
s - A list of strings
wordDictrepresenting the dictionary
Output:
- List of all possible sentences
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
Examples:
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: []
Explanation: No valid segmentation exists.
Solutions
Approach 1: Backtracking with Memoization
Algorithm:
- Use backtracking to try all possible word combinations
- Use memoization to avoid recomputing the same subproblems
- For each position, try all words that match the current prefix
- Recursively solve for the remaining substring
Python:
def wordBreak(s, wordDict):
"""
Backtracking with memoization
Time: O(2^N) in worst case due to all possible combinations
Space: O(2^N) for memoization and result storage
"""
word_set = set(wordDict) # O(1) lookup
memo = {}
def backtrack(start):
# Base case: reached end of string
if start == len(s):
return [[]] # One way to break empty string
# Check memo
if start in memo:
return memo[start]
result = []
# Try all possible words starting from current position
for end in range(start + 1, len(s) + 1):
word = s[start:end]
if word in word_set:
# Word found, recursively solve remaining substring
sub_results = backtrack(end)
# Add current word to each result from remaining substring
for sub_result in sub_results:
result.append([word] + sub_result)
memo[start] = result
return result
# Convert list of words to sentences
word_lists = backtrack(0)
return [' '.join(words) for words in word_lists]
def wordBreak_optimized(s, wordDict):
"""
Optimized version with early termination
Time: O(2^N)
Space: O(2^N)
"""
word_set = set(wordDict)
memo = {}
# First check if word break is possible (Word Break I)
def canBreak(start):
if start == len(s):
return True
if start in memo:
return memo[start]
for end in range(start + 1, len(s) + 1):
if s[start:end] in word_set and canBreak(end):
memo[start] = True
return True
memo[start] = False
return False
if not canBreak(0):
return []
# If breakable, find all combinations
memo.clear()
def findAllBreaks(start):
if start == len(s):
return [[]]
if start in memo:
return memo[start]
result = []
for end in range(start + 1, len(s) + 1):
word = s[start:end]
if word in word_set:
sub_results = findAllBreaks(end)
for sub_result in sub_results:
result.append([word] + sub_result)
memo[start] = result
return result
word_lists = findAllBreaks(0)
return [' '.join(words) for words in word_lists]
# Example usage
print(wordBreak("catsanddog", ["cat","cats","and","sand","dog"]))
# Output: ["cats and dog", "cat sand dog"]
Java:
import java.util.*;
class Solution {
private Set<String> wordSet;
private Map<Integer, List<String>> memo;
/**
* Backtracking with memoization
* Time: O(2^N)
* Space: O(2^N)
*/
public List<String> wordBreak(String s, List<String> wordDict) {
wordSet = new HashSet<>(wordDict);
memo = new HashMap<>();
return backtrack(s, 0);
}
private List<String> backtrack(String s, int start) {
// Check memo
if (memo.containsKey(start)) {
return memo.get(start);
}
List<String> result = new ArrayList<>();
// Base case
if (start == s.length()) {
result.add("");
return result;
}
// Try all possible words starting from current position
for (int end = start + 1; end <= s.length(); end++) {
String word = s.substring(start, end);
if (wordSet.contains(word)) {
List<String> subResults = backtrack(s, end);
for (String subResult : subResults) {
if (subResult.isEmpty()) {
result.add(word);
} else {
result.add(word + " " + subResult);
}
}
}
}
memo.put(start, result);
return result;
}
/**
* Alternative implementation with list of words
* Time: O(2^N)
* Space: O(2^N)
*/
public List<String> wordBreakAlternative(String s, List<String> wordDict) {
Set<String> wordSet = new HashSet<>(wordDict);
Map<Integer, List<List<String>>> memo = new HashMap<>();
List<List<String>> wordLists = backtrackWords(s, 0, wordSet, memo);
List<String> result = new ArrayList<>();
for (List<String> wordList : wordLists) {
result.add(String.join(" ", wordList));
}
return result;
}
private List<List<String>> backtrackWords(String s, int start, Set<String> wordSet,
Map<Integer, List<List<String>>> memo) {
if (memo.containsKey(start)) {
return memo.get(start);
}
List<List<String>> result = new ArrayList<>();
if (start == s.length()) {
result.add(new ArrayList<>());
return result;
}
for (int end = start + 1; end <= s.length(); end++) {
String word = s.substring(start, end);
if (wordSet.contains(word)) {
List<List<String>> subResults = backtrackWords(s, end, wordSet, memo);
for (List<String> subResult : subResults) {
List<String> newResult = new ArrayList<>();
newResult.add(word);
newResult.addAll(subResult);
result.add(newResult);
}
}
}
memo.put(start, result);
return result;
}
}
Go:
// wordBreak - Backtracking with memoization
// Time: O(2^N)
// Space: O(2^N)
func wordBreak(s string, wordDict []string) []string {
wordSet := make(map[string]bool)
for _, word := range wordDict {
wordSet[word] = true
}
memo := make(map[int][][]string)
var backtrack func(start int) [][]string
backtrack = func(start int) [][]string {
if result, exists := memo[start]; exists {
return result
}
var result [][]string
// Base case
if start == len(s) {
return [][]string{{}}
}
// Try all possible words
for end := start + 1; end <= len(s); end++ {
word := s[start:end]
if wordSet[word] {
subResults := backtrack(end)
for _, subResult := range subResults {
newResult := make([]string, 0, len(subResult)+1)
newResult = append(newResult, word)
newResult = append(newResult, subResult...)
result = append(result, newResult)
}
}
}
memo[start] = result
return result
}
wordLists := backtrack(0)
sentences := make([]string, 0, len(wordLists))
for _, wordList := range wordLists {
sentences = append(sentences, strings.Join(wordList, " "))
}
return sentences
}
JavaScript:
/**
* Backtracking with memoization
* Time: O(2^N)
* Space: O(2^N)
*/
function wordBreak(s, wordDict) {
const wordSet = new Set(wordDict);
const memo = new Map();
function backtrack(start) {
// Check memo
if (memo.has(start)) {
return memo.get(start);
}
const result = [];
// Base case
if (start === s.length) {
return [[]];
}
// Try all possible words
for (let end = start + 1; end <= s.length; end++) {
const word = s.substring(start, end);
if (wordSet.has(word)) {
const subResults = backtrack(end);
for (const subResult of subResults) {
result.push([word, ...subResult]);
}
}
}
memo.set(start, result);
return result;
}
const wordLists = backtrack(0);
return wordLists.map(wordList => wordList.join(' '));
}
/**
* With early termination check
* Time: O(2^N)
* Space: O(2^N)
*/
function wordBreakOptimized(s, wordDict) {
const wordSet = new Set(wordDict);
// First check if word break is possible
const canBreak = (start, memo = {}) => {
if (start === s.length) return true;
if (start in memo) return memo[start];
for (let end = start + 1; end <= s.length; end++) {
if (wordSet.has(s.substring(start, end)) && canBreak(end, memo)) {
return memo[start] = true;
}
}
return memo[start] = false;
};
if (!canBreak(0)) return [];
// Find all combinations
const memo = new Map();
function findAll(start) {
if (memo.has(start)) return memo.get(start);
if (start === s.length) return [[]];
const result = [];
for (let end = start + 1; end <= s.length; end++) {
const word = s.substring(start, end);
if (wordSet.has(word)) {
const subResults = findAll(end);
for (const subResult of subResults) {
result.push([word, ...subResult]);
}
}
}
memo.set(start, result);
return result;
}
return findAll(0).map(words => words.join(' '));
}
C#:
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
private HashSet<string> wordSet;
private Dictionary<int, List<string>> memo;
/// <summary>
/// Backtracking with memoization
/// Time: O(2^N)
/// Space: O(2^N)
/// </summary>
public IList<string> WordBreak(string s, IList<string> wordDict) {
wordSet = new HashSet<string>(wordDict);
memo = new Dictionary<int, List<string>>();
return Backtrack(s, 0);
}
private List<string> Backtrack(string s, int start) {
if (memo.ContainsKey(start)) {
return memo[start];
}
List<string> result = new List<string>();
// Base case
if (start == s.Length) {
result.Add("");
return result;
}
// Try all possible words
for (int end = start + 1; end <= s.Length; end++) {
string word = s.Substring(start, end - start);
if (wordSet.Contains(word)) {
List<string> subResults = Backtrack(s, end);
foreach (string subResult in subResults) {
if (string.IsNullOrEmpty(subResult)) {
result.Add(word);
} else {
result.Add(word + " " + subResult);
}
}
}
}
memo[start] = result;
return result;
}
}
Key Insights
- Exponential Combinations: In worst case, can have 2^N combinations
- Memoization Essential: Without memoization, would recompute same subproblems
- Early Termination: Check if any break is possible before finding all breaks
- String Building: Can build result as list of words or concatenated strings
- Backtracking Pattern: Try each valid word, recurse on remaining substring
Edge Cases
- No valid break: Return empty list
- Empty string: Single empty sentence
- Single word: String equals one dictionary word
- Overlapping words: Dictionary has words that are prefixes of others
- Repeated words: Same dictionary word used multiple times
Test Cases
def test_word_break_ii():
test_cases = [
("catsanddog", ["cat","cats","and","sand","dog"],
["cats and dog", "cat sand dog"]),
("pineapplepenapple", ["apple","pen","applepen","pine","pineapple"],
["pine apple pen apple", "pineapple pen apple", "pine applepen apple"]),
("catsandog", ["cats","dog","sand","and","cat"], []),
("a", ["a"], ["a"]),
("", ["a"], []),
]
for s, wordDict, expected in test_cases:
result = set(wordBreak(s, wordDict))
expected_set = set(expected)
assert result == expected_set, f"s='{s}', expected={expected}, got={list(result)}"
print(f"wordBreak('{s}') = {list(result)} ✓")
test_word_break_ii()
Common Mistakes
- Not using memoization: Leads to exponential time without caching
- Wrong string concatenation: Building result strings incorrectly
- Missing base case: Not handling end-of-string properly
- Index errors: Off-by-one errors in substring operations
- Not checking feasibility: Not doing early termination when no solution exists
Follow-up Questions
- Word Break I: Just return true/false if any break is possible
- Minimum breaks: Return minimum number of words needed
- Longest words: Prioritize using longer dictionary words
- Word frequency: Each dictionary word has limited usage count
- Case sensitivity: Handle case-insensitive matching
- Optimization: Can we improve the exponential time complexity?
Interview Tips
- Start with Word Break I: Understand the simpler version first
- Explain exponential complexity: Discuss why this can be 2^N
- Show memoization benefit: Compare with and without memoization
- Handle edge cases: Test with impossible breaks and empty inputs
- Discuss optimization: Early termination and string building strategies
- Code incrementally: Build simple version first, then add optimizations
- Test with examples: Walk through the backtracking process step by step