# 1. Introduction

The *Word Break* problem asks if a given string can be segmented into space-separated sequences of one or more dictionary words. For example, if our dictionary consists of the words {“apple”, “pen”, “applepen”}, then the string “applepenapple” can be segmented as “apple pen apple”.

Using dynamic programming, we can solve this problem efficiently by breaking it down into subproblems.

# 2. Program Steps

1. Initialize a boolean array *dp* of size *n+1* where *n* is the length of the input string. The value at index *i* in *dp* will be *true* if the substring from the start to *i* can be segmented using dictionary words.

2. Mark *dp[0]* as *true* since an empty string can always be segmented.

3. For each index from 1 to *n*, check every substring ending at that index and starting from an index where *dp[j]* is *true*.

4. If the substring is found in the dictionary, mark *dp[i]* as *true*.

5. Continue until we’ve processed the entire string.

6. The value at *dp[n]* gives the answer.

# 3. Code Program

```
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public class WordBreak {
public static boolean wordBreak(String s, Set<String> dict) {
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && dict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
public static void main(String[] args) {
Set<String> dict = new HashSet<>(Arrays.asList("apple", "pen", "applepen"));
String s = "applepenapple";
System.out.println("The string \"" + s + "\" can be segmented: " + wordBreak(s, dict));
}
}
```

### Output:

The string "applepenapple" can be segmented: true

# 4. Step By Step Explanation

1. We use a boolean array *dp* to track if the string up to index *i* can be segmented using dictionary words.

2. For each substring ending at index *i*, we check if it's present in the dictionary and if the substring leading up to it (determined by *dp[j]*) can also be segmented.

3. If both conditions are satisfied, we mark *dp[i]* as *true*.

4. After processing the entire string, if *dp[n]* is *true*, then the whole string can be segmented using dictionary words.

5. In our example, "applepenapple" is segmented as "apple pen apple", and thus the output is *true*.