Can a string be split into dictionary words?

Dynamic programming Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
text, words = "penapple", {"pen", "apple", "pena"}
ok = [True] + [False] * len(text)
for i in range(1, len(text) + 1):
    ok[i] = any(ok[i - len(w)] and text[i - len(w):i] == w
                for w in words if len(w) <= i)
print(ok[3], ok[4], ok[-1])

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A True True True

Right: 'pen' and 'pena' are words, and 'pen' + 'apple' covers the whole string.

Several cut points can be reachable at once, and the table keeps them all instead of committing to one.

Why not the others?
  • B True False True. 'pena' is in the word list.
  • C False False True. 'pen' is the first three letters.

30-second answer

Let ok[i] mean the first i characters can be split. ok[0] is True. For each i, check each allowed word length L: if ok[i - L] holds and the slice of length L ending at i is an allowed word, ok[i] is True. With W distinct word lengths and words up to L long, that is O(n · W · L) time and O(n) memory.

Practise saying it · 45 s. No recording, just a timer

Explain the dictionary split DP.

Say your answer out loud, then check which of these points you covered:

  • ok[i] over prefixes
  • Try each word length
  • O(n · W · L)

Deep dive

Looping over word lengths instead of every earlier cut keeps the work small.

A set of words gives O(L) lookups (hashing the slice).

A trie lets you extend from each ok position letter by letter instead.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def can_split(text: str, words: list[str]) -> bool:
    allowed = set(words)
    lengths = {len(w) for w in allowed}
    ok = [True] + [False] * len(text)  # ok[i]: text[:i] splits
    for i in range(1, len(text) + 1):
        for size in lengths:
            start = i - size
            if start >= 0 and ok[start] and text[start:i] in allowed:
                ok[i] = True
                break
    return ok[-1]

Common mistakes

  • Greedy: taking the longest matching word first fails on cases like 'aaab' style traps.
  • Exploring every split recursively without a cache, which is exponential.

Senior take & follow-ups

Mention the 'check only real word lengths' optimisation.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you list every split?

    Show hint

    Backtracking with a cache of results for each start index.

  2. What if the word list is huge?

    Show hint

    Use a trie, or limit lengths to those present in the list.

What each operation costs: Two Dimensional Arrays

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.