# Word break problem using dynamic programming | faceprep

Program to solve the word break problem is discussed here. Given a dictionary of words and a string, print “True” if the string can be split into the dictionary words if not print “False”.

Sample Input:

5
face placement is thinking focused
focusedthinkingisplacements

Sample Output:

False

Explanation:

The given string and the given dictionary words do not match.

## Algorithm for the word break problem

• Consider each prefix and search it in the dictionary.
• If the prefix is present in the dictionary, recur for rest of the string.
• If the recursive call for rest of the string returns true, return true, otherwise, try with the next prefix.
• After trying all prefixes and none of them resulted in a solution, then, return false.
• This solution involves many overlapping sub-problems.
• A solution using dynamic programming is given below.

Program for the word break problem using dynamic programming is given below.

/* C++ program for the word break problem using dynamic programming */

#include<bits/stdc++.h>
using namespace std;
vector<string> dictionary;
bool ContainsWord(string temp)
{
if(find(dictionary.begin(), dictionary.end(), temp) != dictionary.end())
return true;
else
return false;
}
int main()
{
int n;
cin>>n;
string temp;
for(int i=0;i<n;i++)
{
cin>>temp;
dictionary.push_back(temp);
}
string source;
cin>>source;
int size=source.length();
bool isValid[size+1];
isValid=false;
for(int i=1;i<size+1;i++)
isValid[i]=false;
for(int i=1;i<size+1;i++)
{
if(isValid[i] == false && ContainsWord(source.substr(0,i)))
isValid[i] = true;
if(isValid[i])
{
if(i == size)
break;
for(int j=i+1;j<size+1;j++)
{
if(isValid[j] == false and ContainsWord(source.substr(i,(j-i))))
isValid[j]=true;
if(j == size && isValid[j] == true)
break;
}
}
}
if(isValid[size])
cout<<“True”;
else
cout<<“False”;
}

Test Case 1

I/P
5
face placement is thinking focused
focusedthinkingisplacements
O/P
False

Test Case 2

I/P
5
face placement is thinking focused
focusedthinkingisplacement
O/P
True

Test Case 3

I/P
12
exercise is very bad good for jumping running crying in a park
runninginaparkisverygoodexercise
O/P
True

Test Case 4

I/P
10