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.