In the input of this problem, one sentence is given without spaces,
another dictionary is also provided of some valid English words. We
have to find the possible ways to break the sentence in individual
dictionary words.
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.
Input and Output
Input: A set of valid words as dictionary, and a string where
different words are placed without spaces.
Dictionary: {mobile, sam, sung, man, mango, icecream, and, go, i,
love, ice, cream}
Given String: “ilovemangoicecream”
Output: All possible ways to break the string into given words.
i love man go ice cream
i love man go icecream
i love mango ice cream
i love mango icecream
Algorithm
wordBreak(string, n, result)
Input − Given string, length of the string, the separated strings.
Output − Separate string using a dictionary.
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
#define N 13
using namespace std;
string dictionary[N] = {"mobile","samsung","sam","sung","man","mango", "icecream","and",
"go","i","love","ice","cream"};
int isInDict(string word){ //check whether the word is in dictionary or not
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++) {
string subStr = str.substr(0, i); //get string from 0 to ith location of the string
if (isInDict(subStr)) { //if subStr is found in the dictionary
if (i == n) {
result += subStr; //add substring in the result.
cout << result << endl;
return;
}
wordBreak(str.substr(i, n-i), n-i, result + subStr + " "); //otherwise break rest part
}
}
}
int main() {
string str="iloveicecreamandmango";
wordBreak(str, str.size(),"");
}
i love man go ice cream
i love man go icecream
i love mango ice cream
i love mango icecream