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()];
    }
}