Sign in
Skip to solution
mediumDSA

How do you solve the word break problem?

475 views
01

Understand the problem

Explain word break DP.

dpstrings
02

Attempt it yourself

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

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

dp[i] is true if the prefix of length i can be segmented into dictionary words. For each i, check every split j where dp[j] is true and s[j..i] is in the dictionary. O(n²) with a word set; a trie can speed up substring checks.

Solution ready — 2 min read

Classified // press E to declassify

04

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
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

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

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 70 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track