Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




Edit

Word break problem using dynamic programming | FACE Prep

Published on 10 Mar 2020

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

focused thinking is placements


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 forrest 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


C++

Output
Input - 5
face placement is thinking focused
focusedthinkingisplacements Output - 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


Recommended Programs





If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in
Explore 'c plus plus'
Articles Practice Exercises