LeetCode 139: Word Break

Problem Restatement

We are given:

Return True if s can be segmented into a sequence of one or more dictionary words.

The same dictionary word may be used multiple times.

If no complete segmentation exists, return False.

LeetCode states the task as checking whether s can be segmented into a space-separated sequence of dictionary words. Words may be reused, and dictionary words are unique.

Examples

Example 1:

s = "leetcode"
wordDict = ["leet", "code"]

We can split:

leet | code

Output:

True

Example 2:

s = "applepenapple"
wordDict = ["apple", "pen"]

We can split:

apple | pen | apple

The word "apple" is reused.

Output:

True

Example 3:

s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]

There is no way to split the whole string into valid dictionary words.

Output:

False

Input and Output

Function shape:

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        ...

First Thought: Try Every Split Recursively

A direct approach is to try every dictionary word at the current position.

For example:

s = "leetcode"
wordDict = ["leet", "code"]

At index 0, we can choose "leet" because the string starts with it.

Then we recurse on:

"code"

This works conceptually, but it repeats work.

For a string with many possible prefixes, the recursion branches heavily.

Example:

s = "aaaaaaa"
wordDict = ["a", "aa", "aaa", "aaaa"]

There are many ways to split the same suffix again and again.

We need dynamic programming.

Key Insight

A prefix is breakable if it can be split into:

breakable prefix + dictionary word

Let:

dp[i]

mean:

s[0:i] can be segmented into dictionary words

This uses Python slice notation, where s[0:i] excludes index i.

So:

The answer is:

dp[len(s)]

DP Transition

To compute dp[i], try every split point j before i.

s[0:i] = s[0:j] + s[j:i]

If:

dp[j] == True

and:

s[j:i] in word_set

then dp[i] is also True.

So the transition is:

dp[i] = any(dp[j] and s[j:i] in word_set for j in range(i))

Algorithm

Convert wordDict into a set:

word_set = set(wordDict)

Create a boolean array:

dp = [False] * (n + 1)

Set:

dp[0] = True

Then for each end index i from 1 to n:

1. Try every split point j from 0 to i - 1.
2. If dp[j] is true and s[j:i] is in the dictionary, set dp[i] = True.
3. Stop early for this i.

Return dp[n].

Correctness

dp[0] is true because the empty prefix needs no words.

For every i > 0, the algorithm checks every possible last word of a segmentation of s[0:i].

If there is a valid segmentation, then it has some last word s[j:i]. The prefix before it, s[0:j], must also be segmentable, so dp[j] is true. Since the last word is in the dictionary, the algorithm will set dp[i] to true.

If the algorithm sets dp[i] to true, then there is some split point j where dp[j] is true and s[j:i] is a dictionary word. Therefore, a valid segmentation of s[0:j] followed by s[j:i] gives a valid segmentation of s[0:i].

Thus, each dp[i] correctly says whether s[0:i] can be segmented. Therefore, dp[n] is the correct answer for the whole string.

Complexity

Let:

Basic DP tries all split points.

We can improve practical runtime by only checking split lengths up to the longest dictionary word.

Then each i checks at most L candidates.

Since LeetCode constraints are small enough for this DP, this approach is accepted.

Implementation

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        word_set = set(wordDict)
        max_len = max(len(word) for word in wordDict)

        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True

        for end in range(1, n + 1):
            start_limit = max(0, end - max_len)

            for start in range(start_limit, end):
                if not dp[start]:
                    continue

                if s[start:end] in word_set:
                    dp[end] = True
                    break

        return dp[n]

Code Explanation

We store dictionary words in a set:

word_set = set(wordDict)

This makes membership checks fast.

We also compute the maximum dictionary word length:

max_len = max(len(word) for word in wordDict)

No valid last word can be longer than this.

The DP array has n + 1 entries:

dp = [False] * (n + 1)

The empty prefix is always segmentable:

dp[0] = True

For each end position:

for end in range(1, n + 1):

we only need to try starts that form a word of length at most max_len:

start_limit = max(0, end - max_len)

If the prefix before start cannot be segmented, skip it:

if not dp[start]:
    continue

If the last substring is a dictionary word:

if s[start:end] in word_set:

then this prefix is breakable:

dp[end] = True
break

The final answer is:

return dp[n]

Testing

def run_tests():
    s = Solution()

    assert s.wordBreak("leetcode", ["leet", "code"]) is True

    assert s.wordBreak(
        "applepenapple",
        ["apple", "pen"],
    ) is True

    assert s.wordBreak(
        "catsandog",
        ["cats", "dog", "sand", "and", "cat"],
    ) is False

    assert s.wordBreak(
        "aaaaaaa",
        ["aaaa", "aaa"],
    ) is True

    assert s.wordBreak(
        "cars",
        ["car", "ca", "rs"],
    ) is True

    assert s.wordBreak(
        "bb",
        ["a", "b", "bbb", "bbbb"],
    ) is True

    print("all tests passed")

run_tests()

Test meaning: