Restore Every Valid IP Address
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Restore Every Valid IP Address
Implement `restore_ip_addresses(s)`. Insert exactly three dots into the digit string `s` to form every valid IPv4 address. Each of the four segments must represent an integer from `0` through `255`. A segment may not contain a leading zero unless the segment is exactly `"0"`.
Return all valid addresses in ascending lexicographic order with no duplicates. The source identifies the standard problem by its encoded number but supplies no interview-specific variant; the length bound and deterministic output order below are portable practice assumptions.
## Function Contract
`restore_ip_addresses(s: str) -> list[str]`
## Constraints
- `1 <= len(s) <= 20`
- `s` contains only decimal digits.
- Input digits must be used exactly once and in their original order.
- Return an empty list when no valid address exists.
## Examples
### Example 1
```text
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
```
Both outputs have four valid segments and use every input digit in order.
### Example 2
```text
Input: "0000"
Output: ["0.0.0.0"]
```
Each zero must stand alone because multi-digit segments with a leading zero are invalid.
Overview: Restore every valid IPv4 address by inserting three dots into a string of digits. The task defines segment bounds, leading-zero rules, exact digit use, lexicographic output, impossible cases, and two examples for later cross-language console verification.
Read the full TikTok Software Engineer interview experience this question came from
Insert exactly three dots into the decimal digit string s to form every valid IPv4 address. Use every input digit exactly once in its original order. Each of the four nonempty segments must represent an integer from 0 through 255, and a segment may not have a leading zero unless it is exactly "0". Return all valid addresses without duplicates in ascending lexicographic order, or an empty list when none exists. The source identifies the standard problem by its encoded number but gives no interview-specific variant; the length bound and deterministic output order are portable practice assumptions.
Constraints
- 1 <= len(s) <= 20
- s contains only decimal digits.
- Every output uses all input digits exactly once and in order.
- Each segment is in [0, 255] and has no multi-digit leading zero.
- Return unique addresses in ascending lexicographic order.
Examples
Input: ('25525511135',)
Expected Output: ['255.255.11.135', '255.255.111.35']
Explanation: Both source-example addresses have four valid segments and the sorted order is deterministic.
Input: ('0000',)
Expected Output: ['0.0.0.0']
Explanation: Every zero must stand alone.
Hints
- Each of the four segments contains between one and three digits.
- Prune when the remaining digits cannot fill the remaining segments within those length bounds.