Java Program To Solve Word Break Problem

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
public int wordBreak(String A, ArrayList<String> B) {
int[] result = new int[A.length() + 1];

//for empty string wordbreak is true
result[0] = 1;

for(int i=0; i<A.length(); i++){
for(int j=0; j<=i; j++){
if(result[j] == 1 && B.contains(A.substring(j,i+1))){
result[i+1] = 1;
break;
}
}
}
return result[A.length()];
}
}

Leave a Comment