Word Break – Solution & Complexity

Watch: Word Break with ok[i] by position

Trying every first word and recursing on the rest re-solves the same suffix: 20 a's then a b, with a, aa and aaa, takes 266,079 calls to say no. Remember by position instead. ok[i] means the first i letters split into words; start with ok[0] = true and, from every true position, try each word. On applepenapple that marks 0, 5, 8 and 13, so the answer is true. O(n · words · word length) time, O(n) space.

Solution Walkthrough

  1. Step 1: Understanding the Problem

    • You are given a string s and a list of valid words wordDict.
    • You must decide if s can be cut into pieces where every piece is a dictionary word.
    • Words can be reused, and you must use the whole string with no leftover characters.
  2. Step 2: Spotting Overlapping Subproblems

    • Whether s is breakable depends on whether some prefix is a word and the remaining suffix is also breakable.
    • The same suffix gets asked about repeatedly, so plain recursion does duplicated work.
    • This overlap is the signal to use dynamic programming.
  3. Step 3: Defining the DP State

    • Let dp[i] mean "the first i characters s[0:i] can be segmented".
    • dp[0] is True because the empty string is trivially segmentable.
    • The answer we want is dp[len(s)].
    def word_break(s, wordDict):
        words = set(wordDict)  # O(1) lookups
        dp = [True] + [False] * len(s)
        for i in range(len(s)):
            if not dp[i]:
                continue
            for word in words:
                if s.startswith(word, i):
                    dp[i + len(word)] = True
        return dp[len(s)]
  4. Step 4: Filling the Table

    • For each end position i, look at every split point j < i.
    • If dp[j] is True and the slice s[j:i] is a dictionary word, then dp[i] is reachable.
    • Once we find one valid split we can stop scanning that i.
    def word_break(s, wordDict):
        words = set(wordDict)
        dp = [True] + [False] * len(s)
        for i in range(1, len(s) + 1):
            for j in range(i):
                if dp[j] and s[j:i] in words:
                    dp[i] = True
                    break
        return dp[len(s)]
  5. Step 5: Complexity

    • Time: O(n^2) for the nested loops, times the slice/hash cost.
    • Space: O(n) for the dp array plus the word set.
    • This comfortably handles the constraints for the Word Break problem.

FAQ