The aim is to return all conceivable ways to break the sentence in individual dictionary words given a dictionary dict[] with a list of non-empty words and a non-empty sequence s.
Note: When breaking, a dictionary word may be used more than once.
Examples:
Input: s = “catsanddog” , dict = [“cat”, “cats”, “and”, “sand”, “dog”]
Output:
“cats and dog”
“cat sand dog”
Explanation: The string is split into above 2 ways, in each way all are valid dictionary words.
Input: s = “pineapplepenapple” , dict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”]
Output:
“pine apple pen apple”
“pineapple pen apple”
“pine applepen apple”
Explanation: The string is split into above 3 ways, in each way all are valid dictionary words.
How to put the aforementioned concept into practice:
- To facilitate fast search, turn the dictionary into a hash set.
- A proper phrase has been constructed if the start index surpasses the string’s length (s). To the result, add the current sentence (curr).
- Beginning at start and terminating at every feasible point (end), loop through each substring.
- Verify whether each substring is present in the dictionary (dictSet).
- If legitimate:
- Add the word “curr” to the current sentence.
- Call the function recursively for the remainder of the string (starting at the end).
- To guarantee that the subsequent branch of exploration begins with the proper sentence, restore the state of curr after the recursive call returns.
C++
// C++ implementation to find valid word
// break using Recursion
#include <bits/stdc++.h>
using namespace std;
// Helper function to perform backtracking
void wordBreakHelper(string& s, unordered_set<string>& dictSet,
string& curr, vector<string>& res,
int start) {
// If start reaches the end of the string,
// save the result
if (start == s.length()) {
res.push_back(curr);
return;
}
// 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)) {
string prev = curr;
// Append the word to the current sentence
if (!curr.empty()) {
curr += " ";
}
curr += word;
// Recurse for the remaining string
wordBreakHelper(s, dictSet, curr, res, end);
// Backtrack to restore the current sentence
curr = prev;
}
}
}
// 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());
vector<string> res;
string curr;
wordBreakHelper(s, dictSet, curr, res, 0);
return res;
}
int main() {
string s = "ilikesamsungmobile";
vector<string> dict = {"i", "like", "sam", "sung",
"samsung", "mobile", "ice",
"and", "cream", "icecream",
"man", "go", "mango"};
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
import java.util.*;
class GfG {
// Helper function to perform backtracking
static void wordBreakHelper(String s, HashSet<String> dictSet,
String curr, List<String> res,
int start) {
// If start reaches the end of the string,
// save the result
if (start == s.length()) {
res.add(curr);
return;
}
// 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)) {
String prev = curr;
// Append the word to the current sentence
if (!curr.isEmpty()) {
curr += " ";
}
curr += word;
// Recurse for the remaining string
wordBreakHelper(s, dictSet, curr, res, end);
// Backtrack to restore the current sentence
curr = prev;
}
}
}
// 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);
List<String> res = new ArrayList<>();
String curr = "";
wordBreakHelper(s, dictSet, curr, res, 0);
return res;
}
public static void main(String[] args) {
String s = "ilikesamsungmobile";
List<String> dict = Arrays.asList("i", "like", "sam", "sung",
"samsung", "mobile", "ice",
"and", "cream", "icecream",
"man", "go", "mango");
List<String> result = wordBreak(s, dict);
for (String sentence : result) {
System.out.println(sentence);
}
}
}Python
# Python implementation to find valid
# word break using Recursion
def wordBreakHelper(s, dictSet, curr, res, start):
# If start reaches the end of the string,
# save the result
if start == len(s):
res.append(curr)
return
# 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:
prev = curr
# Append the word to the current sentence
if curr:
curr += " "
curr += word
# Recurse for the remaining string
wordBreakHelper(s, dictSet, curr, res, end)
# Backtrack to restore the current sentence
curr = prev
def wordBreak(s, dict):
# Convert dictionary list to a set
dictSet = set(dict)
res = []
curr = ""
wordBreakHelper(s, dictSet, curr, res, 0)
return res
if __name__=='__main__':
s = "ilikesamsungmobile"
dict = ["i", "like", "sam", "sung",
"samsung", "mobile", "ice",
"and", "cream", "icecream",
"man", "go", "mango"]
result = wordBreak(s, dict)
for sentence in result:
print(sentence)JS
// JavaScript implementation to find valid
// word break using Recursion
// Helper function to perform backtracking
function wordBreakHelper(s, dictSet, curr, res, start) {
// If start reaches the end of the string, save the result
if (start === s.length) {
res.push(curr);
return;
}
// 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 prev = curr;
// Append the word to the current sentence
if (curr.length > 0) {
curr += " ";
}
curr += word;
// Recurse for the remaining string
wordBreakHelper(s, dictSet, curr, res, end);
// Backtrack to restore the current sentence
curr = prev;
}
}
}
// Main function to generate all possible sentence breaks
function wordBreak(s, dict) {
// Convert dictionary array to a Set
let dictSet = new Set(dict);
let res = [];
let curr = "";
wordBreakHelper(s, dictSet, curr, res, 0);
return res;
}
let s = "ilikesamsungmobile";
let dict = ["i", "like", "sam", "sung",
"samsung", "mobile", "ice",
"and", "cream", "icecream",
"man", "go", "mango"];
let result = wordBreak(s, dict);
result.forEach((sentence) => {
console.log(sentence);
});Output
i like sam sung mobile i like samsung mobile