Description
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.
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: []Solution in Python
To solve the problem of adding spaces in a string s to construct sentences where each word is a valid dictionary word from wordDict, we can use a combination of dynamic programming and backtracking. The dynamic programming part helps us determine if a valid segmentation exists, while the backtracking part helps generate all possible sentences.
Approach
- Dynamic Programming Table:
- Create a list
dpwheredp[i]stores the list of words that can end at positioniin the strings. - Initialize
dp[0]to an empty list because an empty string can be segmented trivially.
- Create a list
- Build the DP Table:
- Iterate over each position
iin the strings. - For each word in
wordDict, check if the word matches the substring ending at positioniand updatedp[i]accordingly.
- Iterate over each position
- Backtracking:
- Use backtracking to generate all possible sentences from the DP table.
- Start from the end of the string and recursively build sentences by concatenating words that can end at each position.
Python
from typing import List
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
# Convert the word dictionary to a set for O(1) lookup time
wordSet = set(wordDict)
# DP table where dp[i] will store the list of words that can end at position i
dp = [[] for _ in range(len(s) + 1)]
dp[0] = [""]
# Build the DP table
for i in range(1, len(s) + 1):
for j in range(i):
word = s[j:i]
if word in wordSet and dp[j]:
dp[i].append(word)
# Backtracking to build all possible sentences
def backtrack(index):
if index == 0:
return [""]
result = []
for word in dp[index]:
previous_sentences = backtrack(index - len(word))
for sentence in previous_sentences:
if sentence:
result.append(sentence + " " + word)
else:
result.append(word)
return result
return backtrack(len(s))Detailed Explanation of the Code
- Initialization:
- Convert
wordDictto a setwordSetfor fast lookups. - Create a DP list
dpof sizelen(s) + 1where each element is an empty list.dp[i]will store the list of words that can end at positioni.
- Convert
- Build the DP Table:
- Iterate over each position
ifrom1tolen(s). - For each
jfrom0toi-1, check if the substrings[j:i]is a valid word inwordSetand ifdp[j]is not empty. - If so, append the word to
dp[i].
- Iterate over each position
- Backtracking:
- Define a
backtrackfunction that takes an index and returns all possible sentences that can be formed up to that index. - If the index is
0, return a list with an empty string (base case). - For each word in
dp[index], recursively find all sentences that can be formed up toindex - len(word)and append the current word. - Return the result list.
- Define a
- Return the Result:
- Call
backtrack(len(s))to generate all possible sentences from the DP table.
- Call
Solution in Javascript
JavaScript
/**
* @param {string} s
* @param {string[]} wordDict
* @return {string[]}
*/
var wordBreak = function(s, wordDict) {
// Convert the word dictionary to a set for O(1) lookup time
let wordSet = new Set(wordDict);
// DP array where dp[i] will store the list of words that can end at position i
let dp = new Array(s.length + 1).fill(null).map(() => []);
dp[0] = [""]; // Base case: an empty string is trivially segmented
// Build the DP table
for (let i = 1; i <= s.length; i++) {
for (let j = 0; j < i; j++) {
let word = s.slice(j, i);
if (wordSet.has(word) && dp[j].length > 0) {
dp[i].push(word);
}
}
}
// Backtracking to build all possible sentences
function backtrack(index) {
if (index === 0) {
return [""]; // Base case: return an array with an empty string
}
let result = [];
for (let word of dp[index]) {
let previousSentences = backtrack(index - word.length);
for (let sentence of previousSentences) {
if (sentence) {
result.push(sentence + " " + word);
} else {
result.push(word);
}
}
}
return result;
}
return backtrack(s.length);
};Solution in Java
Java
import java.util.*;
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
// Convert the wordDict list to a set for O(1) lookups
Set<String> wordSet = new HashSet<>(wordDict);
// Create the DP table to store the list of words that can end at each position
List<List<String>> dp = new ArrayList<>();
for (int i = 0; i <= s.length(); i++) {
dp.add(new ArrayList<>());
}
// Base case: an empty string can be segmented trivially
dp.get(0).add("");
// Fill the DP table
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
String word = s.substring(j, i);
if (wordSet.contains(word) && !dp.get(j).isEmpty()) {
dp.get(i).add(word);
}
}
}
// Backtracking function to build all possible sentences
return backtrack(s.length(), dp);
}
// Helper function to perform backtracking
private List<String> backtrack(int index, List<List<String>> dp) {
if (index == 0) {
return Arrays.asList(""); // Base case: return a list with an empty string
}
List<String> result = new ArrayList<>();
for (String word : dp.get(index)) {
List<String> previousSentences = backtrack(index - word.length(), dp);
for (String sentence : previousSentences) {
if (sentence.isEmpty()) {
result.add(word);
} else {
result.add(sentence + " " + word);
}
}
}
return result;
}
}Solution in C#
C#
using System;
using System.Collections.Generic;
public class Solution {
public IList<string> WordBreak(string s, IList<string> wordDict) {
// Convert wordDict to a HashSet for quick lookups
HashSet<string> wordSet = new HashSet<string>(wordDict);
// Initialize DP table: dp[i] will hold the list of words that end at index i
List<List<string>> dp = new List<List<string>>();
for (int i = 0; i <= s.Length; i++) {
dp.Add(new List<string>());
}
// Base case: An empty string can be segmented trivially
dp[0].Add("");
// Fill the DP table
for (int i = 1; i <= s.Length; i++) {
for (int j = 0; j < i; j++) {
string word = s.Substring(j, i - j);
if (wordSet.Contains(word) && dp[j].Count > 0) {
dp[i].Add(word);
}
}
}
// Use backtracking to generate all possible sentences
return Backtrack(s.Length, dp);
}
// Helper function for backtracking
private IList<string> Backtrack(int index, List<List<string>> dp) {
if (index == 0) {
return new List<string> { "" }; // Base case: return a list with an empty string
}
List<string> result = new List<string>();
foreach (string word in dp[index]) {
IList<string> previousSentences = Backtrack(index - word.Length, dp);
foreach (string sentence in previousSentences) {
if (string.IsNullOrEmpty(sentence)) {
result.Add(word);
} else {
result.Add(sentence + " " + word);
}
}
}
return result;
}
}