# Word Break Problem | Dynamic Programming

Word Break Problem: Given a string and a dictionary of words, determine if string can be segmented into a space-separated sequence of one or more dictionary words.

For example,

Input:

Output:

Word b r e a k problem
Word b r e ak problem
Word br e a k problem
Word br e ak problem
Word bre a k problem
Word bre ak problem
Word brea k problem
Word break problem

The idea is to use recursion to solve this problem. We consider all prefixes of the current string one by one and check if the current prefix is present in the dictionary or not. If prefix is a valid word, then we add prefix to the output string and recurse for the remaining string. The base case of the recursion is when string becomes empty, and we print the output string.

Below is C++ and Java implementation of the idea:

## Java

Output:

Word b r e a k problem
Word b r e ak problem
Word br e a k problem
Word br e ak problem
Word bre a k problem
Word bre ak problem
Word brea k problem
Word break problem

There is very famous alternate version of above problem in which we only have to determine if string can be segmented into a space-separated sequence of one or more dictionary words or not, and not actually print all sequences. This version is illustrated below in C++ and Java:

## C++

Output:

String can be segmented

## Java

Output:

String can be segmented

The time complexity of above solution is exponential and auxiliary space used by the program is O(1).

The word break problem has an optimal substructure. We have seen that the problem can be broken down into smaller subproblems which can further be broken down into yet smaller subproblems, and so on. The word break problem also exhibits overlapping subproblems so we will end up solving the same subproblem over and over again. If we draw recursion tree, we can see that the same sub-problems are getting computed again and again.

The problems having optimal substructure and overlapping subproblems can be solved by dynamic programming, in which subproblem solutions are Memoized rather than computed again and again. This method is illustrated below in C++ and Java:

## C++

Output:

String can be segmented

## Java

Output:

String can be segmented

The time complexity of above solution is O(n3) and auxiliary space used by the program is O(n2).     (3 votes, average: 4.33 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest

How is the complexity O(n^2) here ? Guest

Make it HashSet instead of List of strings! Since we are only checking for membership, it’ll boost complexity! Guest

is this permutation or combination?