Insert Spaces to Rebuild a Sentence from Dictionary Words
Company: Microsoft
Role: Applied Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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
```python
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**
```text
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**
```text
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**
```text
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"`.
Overview: A coding question that asks you to insert spaces into a string that lost them so that every piece is a dictionary word, returning the smallest valid sentence or None when no split exists. It tests string segmentation with dictionary lookups, handling of impossible inputs, and a canonical tie-breaking rule.
Read the full Microsoft Applied Scientist interview experience this question came from