Coding interview problems › Dynamic Programming

🪙 Dynamic Programming Medium

Word Break

Word Break explained: decide if a string splits into dictionary words using a 1D DP over prefixes, tested Python solution, pitfalls and a live DP visual.

Also searched as: word break dp · can a string be segmented into dictionary words · word segmentation problem

🪙

Try it live Free

Coin Change (DP)

In the Coin Change lab, watch dp[] fill left to right with each cell built from earlier answers; in Word Break each cell is a yes or no built from earlier prefixes and one dictionary word.

Also useful: Trie & Autocomplete

Open the playground →

The problem

Given a string s and a list of dictionary words, decide whether s can be cut into a sequence of one or more dictionary words. A word may be used more than once.

Inputs = "applepenapple", words = ["apple", "pen"]
OutputTrue

apple + pen + apple

Inputs = "catsandog", words = ["cats", "dog", "sand", "and", "cat"]
OutputFalse

The key insight

It is coin change with words as coins. Let ok[i] mean "the first i characters can be segmented". The prefix of length i works if some earlier cut j works and s[j:i] is a dictionary word. Fill ok from left to right.

Brute force first: Trying every way to cut the string recursively is exponential, because the same suffix gets re-checked from many different cut points.

Step-by-step approach

  1. Put the words in a set for O(1) lookups and note the longest word length.
  2. Create ok of size n + 1 with ok[0] = True (the empty prefix).
  3. For each end i from 1 to n, look back at start points j no further than the longest word.
  4. If ok[j] is true and s[j:i] is in the set, mark ok[i] = True and stop looking.
  5. Return ok[n].

Python solution

PYTHON 3tested
def word_break(s, word_dict):
    words = set(word_dict)
    longest = max(map(len, words), default=0)
    n = len(s)
    ok = [True] + [False] * n          # ok[i]: s[:i] can be segmented
    for i in range(1, n + 1):
        for j in range(max(0, i - longest), i):
            if ok[j] and s[j:i] in words:
                ok[i] = True
                break
    return ok[n]

Complexity

TimeO(n · L²)
SpaceO(n)

For each of n end positions we try up to L start positions (L = longest word), and each slice and hash costs up to O(L).

Common mistakes

Frequently asked questions

What is the time and space complexity of Word Break?

With the longest-word bound, O(n × L²) time, where L is the longest dictionary word, and O(n) space for the DP array plus the word set.

How do I return all possible sentences (Word Break II)?

Use DFS with memoization keyed by start index, returning the list of sentences for each suffix. The output itself can be exponential, so no algorithm is polynomial in the worst case.

Can a trie help in Word Break?

Yes. From each reachable start index, walk the trie along the string and mark every position where a word ends. This avoids building substrings and is useful when the dictionary is large.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Dynamic Programming Coin Change (DP) lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.