Skip to content

139. Word Break

On LeetCode ->

Problem

Determine whether s can be formed by concatenating one or more words from wordDict; words may be reused.

s = "applepenapple"
wordDict = ["apple", "pen"]
segmentation = "apple" + "pen" + "apple"
output = True

Key trick

Use dynamic programming where dp[i] means the prefix s[:i] can be segmented; extend only from valid prefix boundaries.

Trap

  • Greedy matching fails when choosing a valid word prevents a later segmentation.
  • Plain backtracking repeats the same suffixes exponentially.
  • Checking every dictionary word at every position does unnecessary work.

Why is it interesting?

It turns an exponential choice problem into reachability among string boundaries.

Python solution

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        words = set(wordDict)
        lengths = {len(word) for word in words}
        n = len(s)

        # dp[end] is true when s[:end] can be segmented.
        dp = [False] * (n + 1)
        dp[0] = True

        for end in range(1, n + 1):
            for length in lengths:
                start = end - length
                if start >= 0 and dp[start] and s[start:end] in words:
                    dp[end] = True
                    break

        return dp[n]

Let \(L\) be the maximum word length, \(k\) the number of distinct word lengths, and \(W\) the total number of dictionary characters.

  • Time: \(O(W + nkL)\), including Python substring creation.
  • Space: \(O(n + d)\) auxiliary space, where \(d\) is the dictionary size.

Comment on my solution

Your solution is correct: it treats indices as graph nodes and uses visited to avoid exponential repetition.

  • Returning immediately upon reaching n is a good optimization.
  • It scans every dictionary word from every reachable index.
  • Each comparison may inspect the entire word, giving worst-case time \(O(n d L)\).
  • Converting the dictionary to a set and checking only possible word lengths reduces unnecessary comparisons.
  • nxt would be sufficient instead of nxt_idx, but the existing name is still clear.
class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        # "leetcode", ["leet","code"]  -> True
        # "applepenapple", ["apple","pen"]  -> True
        # "catsandog", ["cats","dog","sand","and","cat"] -> False
        n = len(s)
        visited = {0}
        stack = [0]
        while stack:
            idx = stack.pop()
            for word in wordDict:
                nxt_idx = idx + len(word)
                if nxt_idx <= n and word == s[idx:nxt_idx]:
                    if nxt_idx == n:
                        return True
                    if nxt_idx not in visited:
                        visited.add(nxt_idx)
                        stack.append(nxt_idx)
        return False