Restore Valid Addresses by Splitting a Digit String
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
Split a string of decimal digits into exactly `k` segments. Each segment must represent an integer from 0 through 255 and may not contain a leading zero unless the segment is exactly `"0"`. Return every valid address by joining its segments with dots in lexicographic order.
### Function Contract
Implement `restore_addresses(digits, k) -> list[str]`.
### Constraints
- `1 <= len(digits) <= 30` and `1 <= k <= 10`.
- The input contains only characters `0` through `9`.
- Every segment has length between 1 and 3.
- The returned list contains no duplicates.
### Examples
- `digits = "25525511135"`, `k = 4` returns `["255.255.11.135", "255.255.111.35"]`.
- `digits = "0000"`, `k = 4` returns `["0.0.0.0"]`.
```hint Prune by remaining length
If `r` segments remain, the remaining digits must number between `r` and `3r`.
```
```hint Reject a zero prefix immediately
After choosing a segment that begins with zero, do not try a longer version of that segment.
```
### Edge Cases
- A segment value of exactly 255 is valid; 256 is not.
- The requested number of segments may make every split impossible.
- For `k` other than four, the same segment rules still apply.
Overview: Split a digit string into exactly k valid zero-to-255 segments, reject leading zeros, prune impossible branches, and return every dotted result in lexicographic order.
Split a decimal digit string into exactly `k` segments. Each segment must be an integer from 0 through 255 and cannot have a leading zero unless it is exactly `0`. Join valid segments with dots and return every distinct address in lexicographic order.
Constraints
- 1 <= len(digits) <= 30 and digits contains only decimal characters.
- 1 <= k <= 10.
- Each segment has length from 1 through 3 and value from 0 through 255.
- A segment cannot have a leading zero unless it is exactly `0`.
Examples
Input: ('25525511135', 4)
Expected Output: ['255.255.11.135', '255.255.111.35']
Explanation: Both source-example decompositions use four valid segments and are returned lexicographically.
Input: ('0000', 4)
Expected Output: ['0.0.0.0']
Explanation: Every zero must be a one-character segment.
Hints
- If `r` segments remain, the remaining digit count must be between `r` and `3r`.
- After taking a one-character zero segment, do not extend it.