Word Break

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

You are allowed to reuse words in the dictionary an unlimited number of times. You may assume all dictionary words are unique.

Return true because "neetcode" can be split into "neet" and "code".

Return true because "applepenapple" can be split into "apple", "pen" and "apple". Notice that we can reuse words and also not use all the words.

Approach

Use DP where dp[i] means the prefix s[:i] can be segmented. For each i, check any word length l such that dp[i-l] is true and s[i-l:i] is in the dictionary. Use a set and max word length for efficiency.

Why It Works

A valid segmentation of s[:i] must end with some dictionary word; the remainder s[:i-l] must also be segmentable. The DP checks exactly this condition for all positions, so dp[n] is true iff the full string can be segmented.

Complexity

• Time: O(n * L) where L is the max word length
• Space: O(n)

Reference Implementation (Python)

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)
        max_len = max((len(w) for w in wordDict), default=0)
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        for i in range(1, n + 1):
            for l in range(1, min(max_len, i) + 1):
                if dp[i - l] and s[i - l:i] in word_set:
                    dp[i] = True
                    break
        return dp[n]