108.Word Break

MediumBlind 751-D Dynamic Programming · 10/12

Problem

Given a string s and a dictionary wordDict, return true if s can be split into a sequence of one or more dictionary words with nothing left over.

Words may be reused any number of times, and you do not need to use every word.

Examples

Input:  s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: "leet" + "code".

Input:  s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: "apple" + "pen" + "apple" — "apple" is reused.

Input:  s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
Explanation: "cats"+"and" or "cat"+"sand" both leave "og", which is not a word.

Constraints

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and wordDict[i] consist of lowercase English letters.
All strings in wordDict are unique.

💡 Key Insight

Whether the suffix s[i..] can be segmented doesn't depend on how the prefix was split. So define f(i) = "can s[i..] be segmented?": f(n) = true, and f(i) = true if some word w matches at position i and f(i + |w|) is true. That's only n + 1 states. Filling them right-to-left gives O(n · m · L) with m words of length up to L; walking a Trie from each i checks all words at once, cutting it to O(n · L).

Recursion (Brute Force)

TimeO(2ⁿ) in the worst caseSpaceO(n)

Intuition

At position i, try every dictionary word that matches s starting at i. If one of them leads to a successful segmentation of the rest, we're done.

Recurrence: f(i) = OR over w in wordDict with s.startsWith(w, i) of f(i + |w|), with f(n) = true.

Algorithm

dfs(i): if i == n return true.
For each w in wordDict: if s.startsWith(w, i) and dfs(i + w.length()), return true.
Return false.

Visualization

s = "catsandog", dict [cats, dog, sand, and, cat]. Two different splits arrive at the same failing suffix f(7) 'og'.

flowchart TD
    A["f(0) 'catsandog'"] -->|"cat"| B["f(3) 'sandog'"]
    A -->|"cats"| C["f(4) 'andog'"]
    B -->|"sand"| D["f(7) 'og'"]
    C -->|"and"| E["f(7) 'og'"]
    D --> F["no word matches: false"]
    E --> G["no word matches: false"]

For longer inputs like "aaaa...ab" with dict [a, aa, aaa], the number of paths into the same suffix explodes exponentially.

Code

java

import java.util.List;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return dfs(s, 0, wordDict);
    }

    // can s[i..] be split into dictionary words?
    private boolean dfs(String s, int i, List<String> wordDict) {
        if (i == s.length()) {
            return true;
        }
        for (String w : wordDict) {
            if (s.startsWith(w, i) && dfs(s, i + w.length(), wordDict)) {
                return true;
            }
        }
        return false;
    }
}

Complexity

Time: O(2ⁿ) in the worst case — every split point can branch.
Space: O(n) — recursion depth.

Top-Down Memoization

TimeO(n · m · L)SpaceO(n)

Intuition

f(i) has the same answer no matter which split reached i. Cache it in a Boolean[] so every suffix is explored once — in the example above, the second visit to f(7) returns false instantly.

Algorithm

Boolean[] memo of size n (null = unknown).
dfs(i): i == n → true; if cached, return it.
Try each word; store and return true on the first success, otherwise store false.

Dry Run

s = "catsandog"
dfs(0) tries "cat" → dfs(3) tries "sand" → dfs(7): nothing matches → memo[7] = false
       dfs(3) → memo[3] = false
dfs(0) tries "cats" → dfs(4) tries "and" → dfs(7): memo hit = false
       dfs(4) → memo[4] = false
dfs(0) → false

Code

java

import java.util.List;

class Solution {
    private Boolean[] memo;

    public boolean wordBreak(String s, List<String> wordDict) {
        memo = new Boolean[s.length()];
        return dfs(s, 0, wordDict);
    }

    private boolean dfs(String s, int i, List<String> wordDict) {
        if (i == s.length()) {
            return true;
        }
        if (memo[i] != null) {
            return memo[i];
        }
        for (String w : wordDict) {
            if (s.startsWith(w, i) && dfs(s, i + w.length(), wordDict)) {
                return memo[i] = true;
            }
        }
        return memo[i] = false;
    }
}

Complexity

Time: O(n · m · L) — n states, each tries m words with an O(L) startsWith.
Space: O(n) — memo and recursion depth.

Bottom-Up Tabulation

TimeO(n · m · L).SpaceO(n)

Intuition

Fill dp[i] from i = n down to 0. When computing dp[i], every dp[i + |w|] is to the right and already final.

Algorithm

boolean[] dp of size n + 1; dp[n] = true.
For i = n-1 .. 0: for each w, if s.startsWith(w, i) and dp[i + |w|], set dp[i] = true and break.
Return dp[0].

Dry Run

s = "leetcode", dict [leet, code]:

i	0	1	2	3	4	5	6	7	8
s[i]	l	e	e	t	c	o	d	e	–
dp[i]	T	F	F	F	T	F	F	F	T

dp[4]: "code" matches and dp[8] = T. dp[0]: "leet" matches and dp[4] = T.

Code

java

import java.util.List;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[n] = true; // empty suffix is trivially segmented
        for (int i = n - 1; i >= 0; i--) {
            for (String w : wordDict) {
                if (s.startsWith(w, i) && dp[i + w.length()]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[0];
    }
}

Complexity

Time: O(n · m · L).
Space: O(n) — the table (dictionary is input).

Bottom-Up DP with a TrieOptimal

TimeO(n · L + total characters in wordDict)SpaceO(n + total characters in wordDict)

Intuition

Approach 3 re-scans every word at every position. Put the dictionary in a Trie instead: from position i, walk the Trie along s[i], s[i+1], .... Every node marked as a word end at character j means s[i..j] is a word, so check dp[j + 1]. The walk stops as soon as no word continues, so each position costs at most L steps (L ≤ 20) regardless of how many words there are.

Algorithm

Insert every word into a Trie.
dp[n] = true. For i = n-1 .. 0:
- node = root; for j = i .. min(n, i + L) - 1:
  - node = node.next[s[j]]; if null, stop.
  - If node.isWord and dp[j + 1]: dp[i] = true, stop.
Return dp[0].

Dry Run

flowchart LR
    A["i=0, dict trie: cat, cats, and, sand, dog"] --> B["walk c-a-t<br/>'cat' is word, dp[3]?"]
    B -->|"dp[3] = false"| C["walk s<br/>'cats' is word, dp[4]?"]
    C -->|"dp[4] = false"| D["walk a: no child<br/>stop"]
    D --> E["dp[0] = false"]

Code

java

import java.util.List;

class Solution {
    private static class TrieNode {
        TrieNode[] next = new TrieNode[26];
        boolean isWord;
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        TrieNode root = new TrieNode();
        int maxLen = 0;
        for (String w : wordDict) {
            TrieNode node = root;
            for (char c : w.toCharArray()) {
                if (node.next[c - 'a'] == null) {
                    node.next[c - 'a'] = new TrieNode();
                }
                node = node.next[c - 'a'];
            }
            node.isWord = true;
            maxLen = Math.max(maxLen, w.length());
        }

        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[n] = true;
        for (int i = n - 1; i >= 0; i--) {
            TrieNode node = root;
            for (int j = i; j < n && j < i + maxLen; j++) {
                node = node.next[s.charAt(j) - 'a'];
                if (node == null) {
                    break; // no dictionary word continues with s[i..j]
                }
                if (node.isWord && dp[j + 1]) {
                    dp[i] = true; // s[i..j] is a word and the rest splits
                    break;
                }
            }
        }
        return dp[0];
    }
}

Complexity

Time: O(n · L + total characters in wordDict) — each start walks at most L Trie nodes.
Space: O(n + total characters in wordDict) — dp plus the Trie.

Complexity Comparison

Approach	Time	Space
Recursion (Brute Force)	O(2ⁿ)	O(n)
Top-Down Memoization	O(n · m · L)	O(n)
Bottom-Up Tabulation	O(n · m · L)	O(n)
Bottom-Up DP with a Trie	O(n · L + ΣL)	O(n + ΣL)

Common Pitfalls

Greedy matching (always take the longest or first word) — "catsandog"-style inputs need backtracking.
Using a boolean[] memo without a "not computed" state: false is a real answer, so use Boolean[] or a separate visited array.
Forgetting dp[n] = true — without the empty-suffix base case nothing can ever be true.
Building substrings with s.substring(i, j) in a double loop creates O(n²) strings; startsWith(w, i) or a Trie walk avoids that.