Word Break

Difficulty: Medium Source: NeetCode

Problem

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1: Input: s = "leetcode", wordDict = ["leet","code"] Output: true

Example 2: Input: s = "applepenapple", wordDict = ["apple","pen"] Output: true

Example 3: Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: false

Constraints:

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20

Prerequisites

Before attempting this problem, you should be comfortable with:

• Dynamic Programming — boolean DP over string prefixes
• Hashing — fast word lookup in a set
• Substring Matching — checking if s[j:i] is in the dictionary

1. Brute Force (Recursion)

Intuition

Try to peel off a valid word from the front of the string, then recursively solve the rest. If any split leads to a full segmentation, return True. Without memoization, the same suffix is checked many times.

Algorithm

1. If s is empty, return True.
2. For each word in wordDict, if s starts with it, recurse on s[len(word):].
3. Return True if any recursion returns True.

Solution

def wordBreak_brute(s, wordDict):
    word_set = set(wordDict)
    memo = {}

    def dp(start):
        if start == len(s):
            return True
        if start in memo:
            return memo[start]
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in word_set and dp(end):
                memo[start] = True
                return True
        memo[start] = False
        return False

    return dp(0)


print(wordBreak_brute("leetcode", ["leet", "code"]))         # True
print(wordBreak_brute("applepenapple", ["apple", "pen"]))    # True
print(wordBreak_brute("catsandog", ["cats","dog","sand","and","cat"]))  # False
print(wordBreak_brute("aaaaaaa", ["aaaa", "aaa"]))           # True

Complexity

• Time: O(n³) with memoization — n start positions × n end positions × O(n) substring check
• Space: O(n) — memo table

2. Dynamic Programming (Bottom-Up)

Intuition

dp[i] = True if s[:i] can be segmented into words from the dictionary. Build this up from left to right.

For each position i, check all positions j < i: if dp[j] is True and s[j:i] is a word in the dictionary, then dp[i] is True.

This is essentially asking: “Is there a valid cut point j such that the left part is segmentable and the right part s[j:i] is a dictionary word?”

Algorithm

1. Initialize dp = [False] * (n + 1), set dp[0] = True (empty string is trivially segmentable).
2. For each i from 1 to n:
   • For each j from 0 to i:
     • If dp[j] and s[j:i] in word_set: set dp[i] = True, break.
3. Return dp[n].

Solution

def wordBreak(s, wordDict):
    word_set = set(wordDict)
    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

    return dp[n]


print(wordBreak("leetcode", ["leet", "code"]))          # True
print(wordBreak("applepenapple", ["apple", "pen"]))     # True
print(wordBreak("catsandog", ["cats","dog","sand","and","cat"]))  # False
print(wordBreak("aaaaaaa", ["aaaa", "aaa"]))            # True
print(wordBreak("a", ["b"]))                            # False
print(wordBreak("", ["anything"]))                      # True (dp[0])

Complexity

• Time: O(n³) — n² (i, j) pairs × O(n) substring hashing
• Space: O(n) — DP array

Common Pitfalls

Forgetting dp[0] = True. The base case is that the empty string requires no words. Without this, no word in the first position can ever be validated.

Not breaking after finding a valid split. Once dp[i] is set to True, you can break early. Continuing to check other j values is wasted work.

Using wordDict as a list for lookups. Convert wordDict to a set at the start. Checking membership in a list is O(k) per lookup (where k = number of words), but O(1) in a set. The difference matters when wordDict is large.