LeetCode 139 – Word Break

Word Break is where greedy string matching visibly fails and dynamic programming visibly saves it. The problem is short enough to state in a sentence and has a counterexample small enough to write on a whiteboard — which makes it one of the better tests of whether someone reaches for DP because they need it or because they recognise the shape.

The problem

Given a string s and a dictionary of words, return whether s can be segmented into a sequence of one or more dictionary words. Words may be reused.

"leetcode",  ["leet","code"]              -> true
"applepenapple", ["apple","pen"]          -> true    "apple" reused
"catsandog", ["cats","dog","sand","and","cat"] -> false
"", anything                              -> true    the empty segmentation
"aaaaaaa", ["aaaa","aaa"]                 -> true    <- kills the greedy

Why greedy fails

"Take the longest matching prefix and continue" is the natural first idea. On "aaaaaaa" with ["aaaa","aaa"]:

s = "aaaaaa"  (six a's)      dict = ["aaaa", "aaa"]

longest first:  take "aaaa"  -> "aa" remains, not a word  -> FALSE
the truth:      "aaa" + "aaa"                             -> TRUE

Taking the locally best piece strands the remainder. Preferring the shortest match instead just moves the failure to a different input — no fixed preference order works, because the right first cut depends on what comes after it. You have to be able to reconsider, which means backtracking or DP.

The reframing

Ask the same question the grid problems ask — not "how do I cut this string?" but:

Can the first i characters be segmented?

One answer per prefix length, and each follows from earlier ones:

dp[0] = true                          the empty prefix, segmented by taking nothing
dp[i] = true if there is some j < i with
            dp[j] AND s[j..i) in the dictionary

dp[0] = true is doing real work, exactly as in Edit Distance — it is what lets a word matching the whole prefix count. Setting it false makes every answer false.

"leetcode", ["leet","code"]

dp[0] = T
dp[4] = dp[0] and "leet" in dict   -> T
dp[8] = dp[4] and "code" in dict   -> T

Java

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>(wordDict);   // O(1) lookups, not O(dict)

        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;                                   // the empty prefix

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && words.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;                              // one witness is enough
                }
            }
        }

        return dp[s.length()];
    }
}

Converting the list to a HashSet is not tidying. List.contains is a linear scan, and it sits inside a doubly nested loop — leaving it a list turns O(n²) lookups into O(n² · m).

The break matters too: the question is whether any split works, so the first one found settles it.

Python

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        words = set(wordDict)                  # O(1) membership

        dp = [False] * (len(s) + 1)
        dp[0] = True                           # the empty prefix

        for i in range(1, len(s) + 1):
            dp[i] = any(dp[j] and s[j:i] in words for j in range(i))

        return dp[len(s)]

any() short-circuits, so it stops at the first witness just as the break does. Reading it as "is there some earlier split point that works and leaves a word?" is the recurrence in English.

Bounding the inner loop

The inner loop tries every split point, but s[j..i) can only be a dictionary word if its length is at most the longest word. That caps the work:

for j from max(0, i - maxWordLength) to i - 1

On a long string with short words this is a large practical saving — O(n · L) rather than O(n²), where L is the longest word. Worth offering, and worth being clear that it is a constant-factor-style improvement driven by the dictionary rather than a change of algorithm.

Complexity

k is the cost of hashing a substring, which is proportional to its length — worth mentioning, because quoting O(n²) while ignoring that substring construction and hashing are not free is a common slip.

The pattern

"Can the first i characters be built?" is the standard 1-D string DP. Word Break II (140) returns every segmentation, which turns it into backtracking plus memoisation and where the output can be exponential. Palindrome Partitioning (131) is the same question with "is a palindrome" instead of "is in the dictionary" — and it enumerates rather than counts, which is why it is exponential and this is polynomial.

A Trie replaces the substring hashing when the dictionary is large, and it is the right answer if the interviewer pushes on the k factor above.

What the interviewer is checking

• That you show greedy failing rather than asserting it.
• The reframing to "first i characters", and dp[0] = true.
• Converting the dictionary to a set, and why it matters inside a nested loop.
• The short-circuit once one witness is found.
• Empty string, and words being reusable.
• That substring hashing is not free, so the bound is not simply O(n²).
• That you can bound the inner loop by the longest word.