Word Break

Frequency: Reported

Given a dictionary of words and an input string containing no spaces, return a string with spaces inserted so that every token is in the dictionary.

Examples

text

input:  "bloombergisfun", ["bloom", "bloomberg", "is", "fun"]
output: "bloomberg is fun"

If no segmentation exists:

text

input:  "bloombergisfun", ["bloom", "bloomberg", "is"]
output: None/Null

The source also gives:

text

input:  "bloombergisfun", ["bloom", "berg", "bloomberg", "is", "fun"]
output: "bloom berg is fun"

That final input has at least two valid segmentations, but the source does not explain why the split form is selected over "bloomberg is fun" or give a general tie rule.

Commented answer fragment visible in the source

python

# from typing import List

# def wordBreak(s: str, wordDict: List[str]) -> List[List[str]]:
#     wordSet = set(wordDict)
#     hashMap = {}
#
#     def dfs(start):
#         if start == len(s):
#             return [[]]
#
#         if start in hashMap:
#             return hashMap[start]
#
#         results = []
#         for end in range(start + 1, len(s) + 1):
#             word = s[start:end]
#             if word in wordSet:
#                 for rest in dfs(end):
#                     results.append([word] + rest)
#
#         hashMap[start] = results

The screenshot cuts off before the helper returns and before the outer function produces the requested string. The fragment's annotated return type is a list of token lists, which also differs from the prompt's requested string result.