{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Word Break – Solution & Complexity

Interview solutions
/
Word Break

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. 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. 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)
    return dp[len(s)]

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. 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

See also:

Practice Word Break online (run code in the browser)Edit Distance solution (hard)First Unique Character in a String solution (easy)Longest Substring Without Repeating Characters solution (medium)Longest Valid Parentheses solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?