Question:

How to Solve Word Break Problems Using Java

Summary

We will use dynamic programming and recursion to solve the word break problem.

Solution

//User function Template for Java

class Solution

{

public static int wordBreak(int n, String s, ArrayList<String> dictionary )

{

HashSet<String> hs = new HashSet<>(dictionary);

dp = new int[s.length()];

int res = solve(s.length() - 1, s, hs);

return res == 1 ? 1 : 0;

}

static int[] dp;

public static int solve(int i, String s, HashSet<String> hs){

if(i == -1) return 1;

if(dp[i] != 0) return dp[i];

for(int j = i; j >= 0; j--){

String str = s.substring(j, i + 1);

if(hs.contains(str) && solve(j - 1, s, hs) == 1){

dp[i] = 1;

return 1;

}

dp[i] = -1;

return -1;

}

Explanation

Three parameters are required for the public static wordBreak method: an ArrayList of strings dictionary, a string s, and an integer n.
The dictionary list's components are used inside the method to create a HashSet with the name hs.
This hash set is used to efficiently look up words in the dictionary to see if they are there.
The output of the dynamic programming is initially stored in an integer array called dp. It is the same length as the string that was entered.