Word Break Problem
What is Word Break Problem?
The Word Break Problem is a logical puzzle in computer science where we are asked to check whether a given string can be segmented into a sequence of words from a dictionary. For example, if the given string is "ramhaspenandapple" and the dictionary is ["ram", "and", "has", "apple", "pen"], the answer is true because the string can be segmented as "ram has pen and apple".
Solving Word Break Problem using Backtracking Approach
In the input of this problem, one sentence is given without spaces, another dictionary is also provided with some valid English words. We have to find the possible ways to break the sentence into individual dictionary words. The given string and dictionary are as follows −
Dictionary: {ram, samuel, winter, man, mango, icecream, and, i, love, ice, cream}
Given String: "ilovewinterandicecream"
We will try to search from the left of the string to find a valid word when a valid word is found, we will search for words in the next part of that string. All possible ways to break the string into given words are −
i love winter and ice cream i love winter and icecream
One way to solve this problem is to use a backtracking approach. It is a technique that tries different combinations and backtracks if a partial solution is not valid. The basic idea is to start from the beginning of the string and check whether the prefix is a word in the specified dictionary or not. If it is, then we recursively check if the remaining suffix can be segmented into words. If both the prefix and the suffix are valid, then we return true and mark it as a part of the solution. Otherwise, we backtrack and try a different prefix.
Pseudocode
Following is the pseudocode for solving a word break problem using the backtracking approach −
Begin
for i := 0 to n, do
subStr := substring of given string from (0..i)
if subStr is in dictionary, then
if i = n, then
result := result + subStr
display the result
return
wordBreak(substring from (i..n-i), n-i, result, subStr, ‘space’)
done
End
Example
In the following example, we will practically demonstrate how to solve the word break problem.
#include <stdio.h>
#include <string.h>
#define N 13
char *dictionary[N] = {"mobile","samsung","sam","sung","man","mango", "icecream","and", "go","i","love","ice","cream"};
//check whether the word is in dictionary or not
int isInDict(char *word){
for (int i = 0; i < N; i++)
if (strcmp(dictionary[i], word) == 0)
return 1;
return 0;
}
void wordBreak(char *str, int n, char *result) {
for (int i=1; i<=n; i++) {
//get string from 0 to ith location of the string
char subStr[100];
strncpy(subStr, str, i);
subStr[i] = '\0';
//if subStr is found in the dictionary
if (isInDict(subStr)) {
if (i == n) {
//add substring in the result
strcat(result, subStr);
printf("%s
", result);
return;
}
//otherwise break rest part
char newResult[100];
strcpy(newResult, result);
strcat(newResult, subStr);
strcat(newResult, " ");
wordBreak(str + i, n-i, newResult);
}
}
}
int main() {
char str[] = "iloveicecreamandmango";
char result[100] = "";
wordBreak(str, strlen(str), result);
return 0;
}
#include <iostream>
#define N 13
using namespace std;
string dictionary[N] = {"mobile","samsung","sam","sung","man","mango", "icecream","and", "go","i","love","ice","cream"};
//check whether the word is in dictionary or not
int isInDict(string word){
for (int i = 0; i < N; i++)
if (dictionary[i].compare(word) == 0)
return true;
return false;
}
void wordBreak(string str, int n, string result) {
for (int i=1; i<=n; i++) {
//get string from 0 to ith location of the string
string subStr = str.substr(0, i);
//if subStr is found in the dictionary
if (isInDict(subStr)) {
if (i == n) {
//add substring in the result
result += subStr;
cout << result << endl;
return;
}
//otherwise break rest part
wordBreak(str.substr(i, n-i), n-i, result + subStr + " ");
}
}
}
int main() {
string str="iloveicecreamandmango";
wordBreak(str, str.size(),"");
}
import java.util.Arrays;
import java.util.List;
public class Main {
static final List<String> DICTIONARY = Arrays.asList("mobile","samsung","sam","sung","man","mango", "icecream","and", "go","i","love","ice","cream");
//check whether the word is in dictionary or not
public static boolean isInDict(String word){
return DICTIONARY.contains(word);
}
public static void wordBreak(String str, int n, String result) {
for (int i=1; i<=n; i++) {
//get string from 0 to ith location of the string
String subStr = str.substring(0, i);
//if subStr is found in the dictionary
if (isInDict(subStr)) {
if (i == n) {
//add substring in the result
result += subStr;
System.out.println(result);
return;
}
//otherwise break rest part
wordBreak(str.substring(i, n), n-i, result + subStr + " ");
}
}
}
public static void main(String[] args) {
String str = "iloveicecreamandmango";
wordBreak(str, str.length(), "");
}
}
# Define the dictionary
dictionary = ["mobile","samsung","sam","sung","man","mango", "icecream","and", "go","i","love","ice","cream"]
# Check whether the word is in dictionary or not
def isInDict(word):
return word in dictionary
# Function to break the word
def wordBreak(str, n, result):
for i in range(1, n+1):
# Get string from 0 to ith location of the string
subStr = str[:i]
# If subStr is found in the dictionary
if isInDict(subStr):
if i == n:
# Add substring in the result
result += subStr
print(result)
return
# Otherwise break rest part
wordBreak(str[i:], n-i, result + subStr + " ")
# Main function
def main():
str = "iloveicecreamandmango"
wordBreak(str, len(str), "")
# Call the main function
if __name__ == "__main__":
main()
Output
i love ice cream and man go i love ice cream and mango i love icecream and man go i love icecream and mango
