{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Word Break – Solution & Complexity

Interview solutions
/
Word Break

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

See also

Practice Word Break online (run code in the browser)Decode Ways solution (medium)Edit Distance solution (hard)Find All Anagrams in a String solution (medium)First Unique Character in a String solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?