☕ DSA Java Articles

Topics › Recursion and Backtracking › Trying out all Combos / Hard

Word Break

Medium TUF ID 4 A2ZSDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a string s and a list of words wordDict. Decide whether s can be written as a sequence of one or more dictionary words placed back to back. The same word may be used any number of times, and the words in the dictionary are distinct and non-empty.

Constraints: 1 ≤ s.length ≤ 300, 1 ≤ wordDict.length ≤ 1000, 1 ≤ wordDict[i].length ≤ 20, lowercase letters only.

Example 1

s = "leetcode", wordDict = ["leet", "code"]
answer = true       // "leet" + "code"

Example 2

s = "applepenapple", wordDict = ["apple", "pen"]
answer = true       // "apple" + "pen" + "apple"; reuse is allowed

Example 3

s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
answer = false      // "cats"+"and" leaves "og"; "cat"+"sand" leaves "og"

Approach 1: Brute force, recursive splitting

Intuition. Whatever the segmentation looks like, its first piece is a dictionary word that is a prefix of s. So: try each dictionary word; if it matches at the current position, the question reduces to “can the rest be segmented?”, which is the same question on a shorter string. The empty remainder is trivially segmented. This is a plain recursive search over all possible first words.

Greedy does not work here (Example 3 shows two plausible first words that both fail, and "cars" with ["car", "ca", "rs"] shows the longest-match choice failing while a shorter one succeeds), so every alternative has to be explored.

Algorithm.

  1. canBreakFrom(start): if start == s.length() return true.
  2. For each word w: if s starts with w at start and canBreakFrom(start + w.length()), return true.
  3. Return false.
static boolean bruteForce(String s, List<String> wordDict) {
    return canBreakFrom(s, 0, wordDict);
}

private static boolean canBreakFrom(String s, int start, List<String> dict) {
    if (start == s.length()) return true;            // everything before `start` was covered by words
    for (String w : dict) {
        if (!w.isEmpty() && s.startsWith(w, start) && canBreakFrom(s, start + w.length(), dict)) return true;
    }
    return false;
}

Complexity. Time O(2^n · k) in the worst case, where k is the dictionary size: the string "aaaa...ab" with the dictionary ["a", "aa", "aaa"] makes the recursion revisit the same suffix through every composition of the prefix, and all of them eventually fail on the b. Space O(n) for the recursion depth.

The !w.isEmpty() guard protects against an empty dictionary word, which would recurse at the same start for ever.

Approach 2: Better, memoise the start index

Intuition. The brute force is slow only because it solves the same subproblem again and again: the answer for canBreakFrom(start) depends on nothing but start. There are only n + 1 distinct values of start, so caching the result for each turns an exponential tree into at most n + 1 real computations. This is top-down dynamic programming; the recursion is unchanged, it just remembers.

Putting the words in a HashSet lets us ask “is s[start, end) a word?” for each end in O(1) expected time instead of looping over the dictionary.

Algorithm.

  1. Build dict as a HashSet, allocate Boolean[] memo of size n + 1 (null means unknown).
  2. canBreakMemo(start): return true at n; return memo[start] if it is set.
  3. For each end > start: if s[start, end) is in dict and the suffix from end can be broken, store and return true.
  4. Store and return false.
static boolean better(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    Boolean[] memo = new Boolean[s.length() + 1];    // null = not computed yet
    return canBreakMemo(s, 0, dict, memo);
}

private static boolean canBreakMemo(String s, int start, Set<String> dict, Boolean[] memo) {
    if (start == s.length()) return true;
    if (memo[start] != null) return memo[start];
    for (int end = start + 1; end <= s.length(); end++) {
        if (dict.contains(s.substring(start, end)) && canBreakMemo(s, end, dict, memo)) {
            memo[start] = true;
            return true;
        }
    }
    memo[start] = false;
    return false;
}

Complexity. Time O(n² · n) = O(n³) in the worst case: n memo entries, each trying O(n) end positions, each building and hashing a substring of length up to n. Space O(n) for the memo and recursion, plus the dictionary set.

Approach 3: Optimal, bottom-up DP bounded by the longest word

Intuition. Turn the memo around. Let dp[i] be “the prefix s[0, i) can be segmented”. dp[0] is true (empty prefix). For i > 0, the prefix is segmentable exactly when its last word is some s[j, i) in the dictionary and the prefix before it, s[0, j), is itself segmentable: dp[i] = OR over j of (dp[j] AND s[j, i) ∈ dict). Filling i from 1 to n guarantees every dp[j] we read is final.

The bound that makes this fast: a word of length more than maxLen (the longest dictionary word) can never match, so j only needs to go back maxLen positions. With maxLen ≤ 20 the inner loop is tiny regardless of n.

Algorithm.

  1. maxLen = longest word length; dp[0] = true.
  2. For i from 1 to n, for j from i - 1 down to max(0, i - maxLen): if dp[j] and s[j, i) is a word, set dp[i] = true and stop the inner loop.
  3. Return dp[n].
static boolean optimal(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    int maxLen = 0;
    for (String w : dict) maxLen = Math.max(maxLen, w.length());
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;                                    // the empty prefix is trivially segmented
    for (int i = 1; i <= n; i++) {
        for (int j = i - 1; j >= 0 && i - j <= maxLen; j--) {
            if (dp[j] && dict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;                               // one valid last word is enough
            }
        }
    }
    return dp[n];
}

Dry run on s = "leetcode", dict = {leet, code}, maxLen = 4:

i prefix s[0, i) candidate last words s[j, i) with dp[j] true dp[i]
1 l l false
2 le le false
3 lee lee false
4 leet leet (j = 0) true
5 leetc c (j = 4) false
6 leetco co (j = 4) false
7 leetcod cod (j = 4) false
8 leetcode code (j = 4) true

Only j values with dp[j] == true and i - j ≤ 4 matter, which is why rows 5 to 8 list a single candidate each: j = 0 is too far back once i > 4.

Complexity. Time O(n · L · L) where L = maxLen: n positions, at most L candidate j, each substring of length at most L. With the problem’s bounds that is well under a million operations. Space O(n) for dp plus the set.

Edge cases and pitfalls