Word break

Python data engineering interview problem. Difficulty: advanced. Pattern: Dynamic Programming. About 20 minutes. Part of the Pro drill bank.

Decide whether a string can be split into words from a dictionary, reusing words freely. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.

A text parser has a dictionary of reusable words and must decide whether the full input can be segmented without gaps. Return true if the string can be split into one or more consecutive dictionary words. Words may be reused and the empty string is formable. Write word_break(s: str, words: list[str]) -> bool. abcd can be split as ab + cd, so it is true when those words are available. The starter file already contains the function name, harness and print lines. Keep them and fill only the function body.

Requirements

  • Use only complete dictionary words.
  • Cover the entire string with no skipped characters.
  • Avoid recomputing the same suffix results.

Constraints

  • Words can be reused and the return type is bool.
  • The empty string returns true.

Examples

Input: word_break("abcd", ["ab", "abc", "cd"]) Output: True ab + cd works. Taking the longest word first (abc) leaves d, which is not a word.

Topics: lakebench, python, segmentation, memoization.

More Python interview questions · All interview problems · Learn data engineering

advanced

Word break

Interview-style drill: Decide whether a string can be split into words from a dictionary, reusing words freely.

Implement `word_break(s: str, words: list[str]) -> bool`. Return `True` if `s` can be cut into one or more consecutive pieces, each of which is in `words`. A word may be used any number of times. The empty string can always be formed. Strings can have 100 characters or more, so trying every cut recursively without remembering results is too slow.