127. Word Break

Define dp[i] = True iff the prefix s[:i] can be segmented into dictionary words. The last word in any valid segmentation ends at position i, so it starts at some earlier position j where dp[j] was already True and s[j:i] is a dictionary word. Try every split point.

The recurrence

dp[i] is True iff there exists some j with 0 ≤ j < i such that:

• dp[j] is True (the prefix up to j is segmentable), and
• s[j:i] is a word in the dictionary.

Base case: dp[0] = True — the empty prefix is trivially segmentable.

Steps

1. Convert wordDict into a set for O(1) lookup.
2. Initialise dp = [False] * (n + 1) and set dp[0] = True.
3. For i from 1 to n:
   • For j from 0 to i - 1:
     • If dp[j] and s[j:i] is in the dictionary, set dp[i] = True and break the inner loop.
4. Return dp[n].

Walk-through

s = "bookcase", wordDict = ["book", "case"].

Return dp[8] = True. ✓

s = "applepenapple", wordDict = ["apple", "pen"] → walk produces dp[5] = True (apple), dp[8] = True (apple+pen), dp[13] = True (+apple). Return True.

s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] → no segmentation reaches dp[9]. Return False.

Why we break early on a match

Once we find a valid split for dp[i], we don't need to keep searching — we already know dp[i] = True. The break trims the inner loop at the first hit, useful for sparse-match strings.

Edge cases

• Empty string: dp[0] = True, return True.
• No valid split: dp[n] = False, return False.
• Single-letter words: still O(n²) substring checks; the algorithm handles it naturally.

Optimisation

Instead of iterating j = 0..i-1, we can iterate j = i - L_max..i-1 where L_max is the longest word in the dictionary — since any longer substring can't be a single dictionary word. That bounds the inner loop, useful when L_max ≪ n.

Complexity

• Time: O(n² · m) worst case — the substring s[j:i] is O(i-j) to construct and O(L) to hash for the set lookup. With sufficient bounds this often runs much faster in practice.
• Space: O(n) for dp, plus O(W) for the word set.

import java.util.*;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && words.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}