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
You are given a string `s` whose spaces were lost and a list of words `dictionary`. Insert spaces into `s` so that it splits into a sequence of words that all appear in `dictionary`, and return the resulting sentence. Dictionary words may be used any number of times.
**Rules**
- A valid sentence is a sequence of 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.
- If no valid sentence exists, return `None` (`null` in JavaScript and Java; `std::nullopt` in C++, where the return type is `std::optional<std::string>`).
**Example 1**
```text
Input: s = "icecreamcone", dictionary = ["ice", "cream", "icecream", "cone", "creamcone"]
Output: "ice cream cone"
```
The valid sentences are `"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.
**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.
No length or count in this problem exceeds 2^31 - 1, so 32-bit integers suffice in every language.
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
Input: ('icecreamcone', ['ice', 'cream', 'icecream', 'cone', 'creamcone'])
Expected Output: 'ice cream cone'
Explanation: Source example 1: shortest first word ice, then cream beats creamcone at the second word.
Input: ('goodday', ['good', 'go', 'odd'])
Expected Output: None
Explanation: Source example 2: after good the rest is day, after go odd the rest is ay; no split.
Hints
- Every valid sentence spells exactly the same letters, so two candidate sentences first differ where one of them places a space and the other continues a word.
- Committing to the shortest matching word can leave a remainder that no sequence of dictionary words covers; think about what you need to know about each remaining suffix before committing.
- No dictionary word is longer than 20 letters, which limits how many words can start at any given position.