- Optimal Substructure: The answers to smaller subproblems can be used to determine the answer to the word break problem. In particular, the challenge reduces to figuring out whether the substring s[start..end] constitutes a legitimate word and combining it with valid sentence breaks for the remaining substring s[end..n] for any given starting index start.
The recursive relation can be expressed as follows:
Check if the term is present in the dictionary using dictSet.count(s.substr(start, end – start)) for each substring s[start..end] where end > start.
For any wordBreakHelper(s, dictSet, memo, end) result that is valid:
Just add the term if it’s empty.
If not, use a space to concatenate the term with the sub-sentence.
- Subproblems That Overlap: The same subproblems are tackled again when recursion is used to solve the word break problem. For instance, wordBreakHelper(s, dictSet, memo, start) would recalculate results for the same start index in various recursion branches if we compute it for a specific start. The results of wordBreakHelper(s, dictSet, memo, start) are stored in a memo map with the index start as the key and a list of acceptable sentence breaks beginning from that index as the value in order to prevent recomputation.
C++
// C++ implementation to find valid word
// break using Recursion and Memoization
#include <bits/stdc++.h>
using namespace std;
// Helper function to perform backtracking with memoization
vector<string> wordBreakHelper(string& s, unordered_set<string>& dictSet,
unordered_map<int, vector<string>>& memo,
int start) {
// If the result for this index is already
// computed, return it
if (memo.count(start)) {
return memo[start];
}
vector<string> result;
// If start reaches the end of the string,
// add an empty string to signify a valid sentence
if (start == s.length()) {
result.push_back("");
return result;
}
// Try every possible substring from the current index
for (int end = start + 1; end <= s.length(); ++end) {
string word = s.substr(start, end - start);
// Check if the word exists in the dictionary
if (dictSet.count(word)) {
// Recurse for the remaining string
vector<string> subSentences
= wordBreakHelper(s, dictSet, memo, end);
// Append the current word to each valid sub-sentence
for (string& sub : subSentences) {
if (sub.empty()) {
result.push_back(word);
} else {
result.push_back(word + " " + sub);
}
}
}
}
// Memoize the result for the current index
memo[start] = result;
return result;
}
// Main function to generate all possible sentence breaks
vector<string> wordBreak(string s, vector<string>& dict) {
// Convert dictionary vector to an unordered set
unordered_set<string> dictSet(dict.begin(), dict.end());
unordered_map<int, vector<string>> memo;
return wordBreakHelper(s, dictSet, memo, 0);
}
int main() {
string s = "catsanddog";
vector<string> dict = {"cat", "cats",
"and", "sand", "dog"};
vector<string> result = wordBreak(s, dict);
for (string sentence : result) {
cout << sentence << endl;
}
return 0;
}Java
// Java implementation to find valid
// word break using Recursion and Memoization
import java.util.*;
class GfG {
// Helper function to perform backtracking with memoization
static List<String> wordBreakHelper(String s, HashSet<String> dictSet,
Map<Integer, List<String>> memo,
int start) {
// If the result for this index is already
// computed, return it
if (memo.containsKey(start)) {
return memo.get(start);
}
List<String> result = new ArrayList<>();
// If start reaches the end of the string,
// add an empty string to signify a valid sentence
if (start == s.length()) {
result.add("");
return result;
}
// Try every possible substring from the current index
for (int end = start + 1; end <= s.length(); ++end) {
String word = s.substring(start, end);
// Check if the word exists in the dictionary
if (dictSet.contains(word)) {
// Recurse for the remaining string
List<String> subSentences
= wordBreakHelper(s, dictSet, memo, end);
// Append the current word to each valid sub-sentence
for (String sub : subSentences) {
if (sub.isEmpty()) {
result.add(word);
} else {
result.add(word + " " + sub);
}
}
}
}
// Memoize the result for the current index
memo.put(start, result);
return result;
}
// Main function to generate all possible sentence breaks
static List<String> wordBreak(String s, List<String> dict) {
// Convert dictionary vector to a HashSet
HashSet<String> dictSet = new HashSet<>(dict);
Map<Integer, List<String>> memo = new HashMap<>();
return wordBreakHelper(s, dictSet, memo, 0);
}
public static void main(String[] args) {
String s = "catsanddog";
List<String> dict = Arrays.asList("cat", "cats",
"and", "sand", "dog");
List<String> result = wordBreak(s, dict);
for (String sentence : result) {
System.out.println(sentence);
}
}
}Python
# Python implementation to find valid
# word break using Recursion and Memoization
def wordBreakHelper(s, dictSet, memo, start):
# If the result for this index is already
# computed, return it
if start in memo:
return memo[start]
result = []
# If start reaches the end of the string,
# add an empty string to signify a valid sentence
if start == len(s):
result.append("")
return result
# Try every possible substring from the current index
for end in range(start + 1, len(s) + 1):
word = s[start:end]
# Check if the word exists in the dictionary
if word in dictSet:
# Recurse for the remaining string
subSentences = wordBreakHelper(s, dictSet, memo, end)
# Append the current word to each valid sub-sentence
for sub in subSentences:
if sub:
result.append(word + " " + sub)
else:
result.append(word)
# Memoize the result for the current index
memo[start] = result
return result
def wordBreak(s, dict):
# Convert dictionary list to a set
dictSet = set(dict)
memo = {}
return wordBreakHelper(s, dictSet, memo, 0)
if __name__ == '__main__':
s = "catsanddog"
dict = ["cat", "cats", "and", "sand", "dog"]
result = wordBreak(s, dict)
for sentence in result:
print(sentence)JS
// JavaScript implementation to find valid
// word break using Recursion and Memoization
// Helper function to perform backtracking
// with memoization
function wordBreakHelper(s, dictSet, memo, start) {
// If the result for this index is already
// computed, return it
if (memo.has(start)) {
return memo.get(start);
}
let result = [];
// If start reaches the end of the string,
// add an empty string to signify a valid sentence
if (start === s.length) {
result.push("");
return result;
}
// Try every possible substring from the current index
for (let end = start + 1; end <= s.length; ++end) {
let word = s.substring(start, end);
// Check if the word exists in the dictionary
if (dictSet.has(word)) {
let subSentences
= wordBreakHelper(s, dictSet, memo, end);
// Append the current word to each
// valid sub-sentence
for (let sub of subSentences) {
if (sub.length > 0) {
result.push(word + " " + sub);
} else {
result.push(word);
}
}
}
}
// Memoize the result for the current index
memo.set(start, result);
return result;
}
// Main function to generate all possible sentence breaks
function wordBreak(s, dict) {
// Convert dictionary array to a Set
let dictSet = new Set(dict);
// Map for memoization
let memo = new Map();
return wordBreakHelper(s, dictSet, memo, 0);
}
let s = "catsanddog";
let dict = ["cat", "cats", "and", "sand", "dog"];
let result = wordBreak(s, dict);
result.forEach((sentence) => {
console.log(sentence);
});Output
cat sand dog cats and dog