Given a string A and a dictionary of words B, find out if A can be segmented into a space-separated sequence of dictionary words.

`Input:`

A = "myinterviewtrainer",

B = ["trainer", "my", "interview"]

Output:

1 ("myinterviewtrainer" can be segmented as "my interview trainer")

Input:

A = "cc"

B = ["ccc"]

Output:

0 ("cc" can't be segmented as "ccc")

Word break problem can be solved using dynamic programming. We solved the problem in bottom up manner. The result array contains n+1 elements where n is length of A. The base case of empty string (“”) is true. Then we begin with the first letter of A & loop till end. There is one inner loop, so time complexity is O(n^2). I am not considering time complexity of finding the substring in List B. It can be converted to Map & find Operation can be done in O(1).

1 |
import java.util.*; |