Word Break: the idea to remember.

The core insight

Mark a prefix reachable when a reachable earlier boundary is followed by a dictionary word.

Why it works

Every valid segmentation has a last word. Testing all possible last boundaries covers every segmentation.

The mistake to avoid

A greedy longest matching prefix can get stuck. Java substring creation and hashing cost time proportional to its length.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

boolean wordBreak(String s, List<String> words) {
    Set<String> dict = new HashSet<>(words);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int end = 1; end <= s.length(); end++) {
        for (int start = 0; start < end; start++) {
            if (dp[start] && dict.contains(s.substring(start, end))) {
                dp[end] = true;
                break;
            }
        }
    }
    return dp[s.length()];
}

Make the next connection