Domain 2MediumCORE

Word Break

We are asked to determine feasibility rather than construct the solution itself (unlike Word Break II). We need a boolean result: True if string s can be fully segmented into words from wordDict, otherwise False.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Dynamic Programming

139. Word Break

Model: qwen3.5:9b
Topics: Dynamic Programming
FAANG asked: 1
Acceptance rate: 41.9%


Problem Breakdown

We are asked to determine feasibility rather than construct the solution itself (unlike Word Break II). We need a boolean result: True if string s can be fully segmented into words from wordDict, otherwise False.

Inputs:

  1. String s: The target text to segment (length <= 300).
  2. List of strings wordDict: Allowed dictionary entries (size <= 1000).

Outputs: Boolean value indicating segmentation success.

Implicit Constraints & Edge Cases:

  • Reuse allowed: Words in the dict can be used multiple times (e.g., “applepenapple” -> apple, pen, apple).
  • Empty segments not valid: We cannot have empty strings between words; every character must belong to a word.
  • Partial matches don’t count: If s ends with characters that aren’t part of any dictionary word starting from the last split point, it fails immediately for that path.
  • Set vs List: Converting wordDict to a set is critical for O(1)O(1) lookup time during checks.

Intuition

A naive approach would be recursion: try splitting at every possible index and recursively check if both parts are valid words or further segments of the dictionary.

Why Brute Force Fails: This leads to an exponential explosion, roughly O(2N)O(2^N). For example, with s = "aaaaa" and dict containing "aa", we have many overlapping subproblems (checking if index 0-5 is valid vs checking index 1-6). We recompute the same substring validity repeatedly.

Key Insight: This exhibits optimal substructure and overlapping subproblems—hallmarks of Dynamic Programming (DP). If a prefix s[0...i] can be segmented, we don’t need to check it again later; we just store that result in an array (dp[i]).

We define dp[i] as “True” if the substring s[:i] can be successfully broken down. We iterate through each character of s, and for every position, we ask: “Can I reach this point from a previously valid split point using one word?”

Approach

  1. Preprocessing: Convert wordDict to a set (word_set) for O(1)O(1) average time complexity lookups. This is non-negotiable for performance in Python due to hashing overhead on lists.
  2. DP State Initialization: Create an array dp of size len(s) + 1. Initialize all values as False, except dp[0] = True. The base case represents the empty string before any characters, which is trivially valid (length 0).
  3. Iteration Logic:
    • Iterate through each index i from 1 to len(s). This represents the end of a potential word segment.
    • To determine if dp[i] can be true, we look backwards at previous indices j < i. These represent start points where a valid segmentation ended previously (dp[j] == True).
    • We check if the substring between s[j:i] exists in our set. If it does and dp[j] is true, then dp[i] = True.
  4. Optimization: Since dictionary words have a maximum length of 20 (per constraints), we don’t need to scan all previous indices j < i. We only check the last 20 characters back from i. This keeps complexity low even if N was larger, though for N=300 it’s not strictly necessary.
  5. Early Exit: If at any point dp[i] becomes true (and we are iterating forward), we can stop checking other previous indices for that specific i because one valid segmentation is sufficient to make the current position reachable.

Complexity Analysis

Time Complexity: O(N⋅L)O(N \cdot L) or effectively O(N2)O(N^2). Where N is string length and L is max word length (bounded by 20). In a standard implementation without the explicit length limit optimization, it’s often cited as O(N2)O(N^2) because we check substrings. With Python slicing being linear in substring length (O(Lword)O(L_{word})), checking all previous indices makes it roughly proportional to N * L. Given constraints (L <= 20), this is practically linear relative to N for the purpose of interview analysis, but strictly O(N2)O(N^2) if we consider worst-case string slicing costs.

Space Complexity: O(N+M⋅L)O(N + M \cdot L). We use an array dp of size N. The set takes space proportional to dictionary words (MM). Since constraints are small (300 chars, 1000 dict entries), this fits easily within memory limits.

Solution

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # Convert list to set for O(1) lookups
        word_set = set(wordDict)
        
        n = len(s)
        # dp[i] indicates if substring s[0:i] can be segmented into dictionary words
        dp = [False] * (n + 1)
        
        # Base case: empty string is valid segmentation of length 0
        dp[0] = True
        
        for i in range(1, n + 1):
            # Optimization: Only check substrings ending at current index 'i' 
            # with lengths up to the maximum word length (20 per constraints).
            # This avoids unnecessary checks on long prefixes that can't be words.
            max_len = min(i, 20) 
            
            for j in range(max(0, i - max_len), i):
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break # Found a valid path to 'i', no need to check other splits
            
        return dp[n]

Edge Cases Handled

  • Empty String: Constraints state s.length >= 1, so this case is not tested per problem definition, but the code handles it naturally (returns True for empty string).
  • No Matches Found: If no combination of words covers the string, dp[n] remains False.
  • Word Longer than Remaining String: The loop range range(max(0, i - max_len), i) ensures we don’t slice beyond available characters or check lengths exceeding 20.
  • Dictionary with Duplicates: Converting to a set removes duplicates automatically without affecting correctness (since reuse is allowed).
  • Single Character Words: The logic handles single character words correctly as j will be adjacent to i.