Bloomberg Interview Question: Word Break (Insert Spaces)

Problem

Given:

• a dictionary of valid words
• an input string with no spaces

Return a spaced string so that every segment is a dictionary word.

Example:

Input string: "bloombergisfun"
Dictionary: ["bloom", "bloomberg", "is", "fun"]
Output: "bloomberg is fun"

Approach

This is the classic Word Break problem.

A robust solution uses DP:

• dp[i] indicates whether s[:i] can be segmented.
• parent[i] stores the previous cut position to reconstruct one solution.

Python (DP + reconstruction)

def word_break_one(s: str, word_dict: list[str]) -> str:
    word_set = set(word_dict)
    n = len(s)

    dp = [False] * (n + 1)
    parent = [-1] * (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 word_set:
                dp[i] = True
                parent[i] = j
                break

    if not dp[n]:
        return ""

    parts = []
    i = n
    while i > 0:
        j = parent[i]
        parts.append(s[j:i])
        i = j

    return " ".join(reversed(parts))

Complexity

• Time: O(n^2)
• Space: O(n)

Need interview help? Contact OA VO Service

• 📧 Email: [email protected]
• 📱 Phone: +86 17863968105

Need real interview questions? Contact WeChat: Coding0201 to get the questions.