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