Insert Spaces to Rebuild a Sentence from Dictionary Words

You are given a string s whose spaces were lost and a list of dictionary words. Insert spaces into s so that it splits into a sequence of words that are all in the dictionary, and return the resulting sentence. Dictionary words may be used any number of times. If no such split exists, return None.

Function Signature

def reconstruct_sentence(s: str, dictionary: list[str]) -> str | None:

Rules

• A valid sentence is words w1, ..., wm (with m >= 1) joined by single spaces, where every word is in dictionary and the concatenation w1 + ... + wm equals s.
• If several valid sentences exist, return the smallest one under ordinary string comparison, where the space character sorts before every lowercase letter. Because every valid sentence spells the same letters, this is the same as preferring the shortest possible first word, then the shortest possible second word, and so on.
• Return None when no valid sentence exists.

Constraints

• 1 <= len(s) <= 2000
• 1 <= len(dictionary) <= 1000
• 1 <= len(word) <= 20 for every dictionary word
• s and every dictionary word consist only of lowercase English letters a to z.
• Dictionary words are distinct.

Examples

Example 1

Input: s = "icecreamcone", dictionary = ["ice", "cream", "icecream", "cone", "creamcone"]
Output: "ice cream cone"

There are three valid sentences: "ice cream cone", "ice creamcone" and "icecream cone". The first is the smallest: it starts with the shorter word "ice", and its second word "cream" is shorter than "creamcone".

Example 2

Input: s = "goodday", dictionary = ["good", "go", "odd"]
Output: None

After "good" the rest is "day", and after "go" and "odd" the rest is "ay"; neither is a dictionary word, so no split works.

Example 3

Input: s = "abab", dictionary = ["ab", "a", "b"]
Output: "a b a b"

The valid sentences are "a b a b", "a b ab", "ab a b" and "ab ab"; words may repeat, and the smallest is "a b a b".