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[0]=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
learn about us data practice video facebook career internship begin
careerinternshipbeginaboutus
O/P
True

Test Case 5

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