The Vocabulary Test

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
LinkedIn

Problem

A search-indexing step normalizes raw queries by checking whether a string s can be rebuilt as a gapless, back-to-back run of terms drawn from an approved vocabulary word_dict, reusing any term as many times as needed. Return whether at least one such full reconstruction exists with no characters left over; an empty s qualifies trivially.

Every character has to come from a word you already know.

Example 1

Input:

s = "leetcode", word_dict = ["leet","code"]

Output:

true

Example 2

Input:

s = "applepenapple", word_dict = ["apple","pen"]

Output:

true

Worked solution and explanation

What this really is

Strip off the vocabulary costume and this is a reachability question over the string's positions: can you walk from index 0 to the end, each hop consuming a chunk that happens to be a known word? The skill being probed is whether you resist the urge to greedily grab a word and commit to it. Take the longest match at each step and you will confidently return the wrong answer on inputs where a shorter early word was the only path that survives to the end.

Building it

Step 1: Put the vocabulary in a set

Membership is the inner-loop hot path, so pay the one-time cost to turn word_dict into a set. A list check is O(k) per probe and you do O(n^2) probes; the set makes each one O(1).

Step 2: Fill the reachability table left to right

Seed reachable[0] = True: the empty prefix is always coverable, which is also why an empty s returns True for free. Then for each end position, scan every earlier start; if that start was reachable and the slice between them is a word, this end is reachable too. Break the inner scan the instant you mark it, since one witness is enough.

Step 3: Read the last cell

The answer is simply whether the final position is reachable. reachable[len(s)] being True means some chain of words consumed the whole string with nothing left over.

The solution

Position reachability with set lookup
def word_break_check(s: str, word_dict: list) -> bool:
    vocab = set(word_dict)
    n = len(s)
    reachable = [False] * (n + 1)
    reachable[0] = True
    for end in range(1, n + 1):
        for start in range(end):
            if reachable[start] and s[start:end] in vocab:
                reachable[end] = True
                break
    return reachable[n]

Each end position opens as soon as one reachable start can hop to it.

Greedy longest-match
Pick the longest word at each cursor and advance. Fast and intuitive, but a single early commitment can dead-end a string that was actually segmentable a different way. No clean way to recover without backtracking.
Reachability table
Keep every reachable position alive at once. No commitment to undo, the whole search is two loops and a slice, and the answer falls out of the last cell. Same worst-case work, none of the wrong answers.

Common follow-up questions