Word Break Problem: Dynamic Programming Solution

By /

Word Break (LeetCode 139) is a string DP problem that tests whether you can partition a string using a given dictionary. It combines dynamic programming with string matching and appears frequently at Google, Amazon, and Facebook.

Problem

Given a string s and a dictionary of words, determine if s can be segmented into a space-separated sequence of dictionary words.

s = "leetcode", wordDict = ["leet","code"]
Output: True ("leet" + "code")

s = "applepenapple", wordDict = ["apple","pen"]
Output: True ("apple" + "pen" + "apple")

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

DP Solution

def word_break(s: str, word_dict: list[str]) -> bool:
    """
    dp[i] = True if s[:i] can be formed from wordDict.
    Transition: dp[i] = any(dp[j] and s[j:i] in wordSet) for j in 0..i-1
    Time: O(n^2 * L) where L = max word length, Space: O(n + |wordDict|)
    """
    word_set = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # Empty prefix is always valid

    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break  # No need to check further for this i

    return dp[n]

# Optimized: only check suffixes up to max word length
def word_break_optimized(s: str, word_dict: list[str]) -> bool:
    word_set = set(word_dict)
    max_len = max(len(w) for w in word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True

    for i in range(1, n + 1):
        # Only check substrings that could be valid words
        for j in range(max(0, i - max_len), i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break

    return dp[n]

Return All Valid Sentences (LeetCode 140)

def word_break_ii(s: str, word_dict: list[str]) -> list[str]:
    """
    Return all ways to segment s into dictionary words.
    Memoization prevents recomputing the same suffix multiple times.
    Time: O(n^2 * 2^n) worst case (exponential number of results)
    """
    from functools import lru_cache
    word_set = set(word_dict)

    @lru_cache(maxsize=None)
    def dp(start):
        if start == len(s):
            return ['']  # Base case: reached end — one empty path

        result = []
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in word_set:
                for suffix in dp(end):
                    result.append(word + ('' if suffix == '' else ' ' + suffix))

        return result

    return dp(0)

print(word_break_ii("catsanddog", ["cat","cats","and","sand","dog"]))
# ["cats and dog", "cat sand dog"]

Connection to Coin Change Pattern

Word Break is structurally identical to Coin Change:

  • Coin Change: can we sum coins to reach amount N?
  • Word Break: can we concatenate words to reach string s?

Both have dp[0] = True base case and check all “coins”/”words” at each position. The key difference is the state representation: integer index vs string prefix.

Practice Problems

  • LeetCode 139: Word Break (boolean)
  • LeetCode 140: Word Break II (all sentences)
  • LeetCode 472: Concatenated Words (all words that are concatenations of shorter words)

Related DP Problems

  • Coin Change — Word Break is coin change on strings: words are “coins”, string length is the “amount”; same unbounded knapsack pattern
  • Edit Distance — both are string DP problems with matching/skipping decisions; understanding LCS and edit distance builds the intuition for word break
Scroll to Top