mediumDSA

How do you solve the word break problem?

Q: How do you solve the word break problem?

**Intuition.** dp[i] answers "can the first i characters be split into dictionary words?" It's true when some earlier split point j is itself breakable ( dp[j] ) **and** the chunk s[j..i] is a word. Build dp left to right; dp[n] is the answer. dp[i] true if some dp[j] true and s[j..i] is a word leet <re

475 views

Understand the problem

Explain word break DP.

dpstrings

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Boolean DP over split points

Run Playground

def word_break(s, word_dict):
    words = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[n]


# --- demo ---
print(word_break('leetcode', ['leet', 'code']))                       # True
print(word_break('applepenapple', ['apple', 'pen']))                  # True
print(word_break('catsandog', ['cats', 'dog', 'sand', 'and', 'cat'])) # False

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you solve the house robber problem?

How do you detect a cycle in a linked list?