Word break problem using dynamic programming | faceprep

Word break problem using dynamic programming | faceprep

Program to solve the word break problem is discussed here.

Word break problem using dynamic programming


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.


face prep pro ad bannerClick here to learn more about FACE Prep PRO


Program for the word break problem using dynamic programming

@@coding::1@@


Recommended Programs


Word break problem using dynamic programming