hardBacktrackingPure DSA~30 min
All Valid IPv4 Addresses From a Digit String
Given a string of digits, insert three dots to form every possible valid IPv4 address. Each of the four parts must be 0-255 with no leading zeros.
Problem
Given a string s containing only digits, return all possible valid IPv4 addresses formed by inserting dots into s. A valid part is between 0 and 255 inclusive and cannot have leading zeros (except the single digit 0). You may not reorder or remove digits.
Input
A digit string s.
Output
A list of all valid IPv4 address strings.
Constraints
- 1 <= s.length <= 20
- s consists of digits only.
- Exactly four parts separated by dots.
Examples
Example 1
Input
s = "25525511135"
Output
["255.255.11.135","255.255.111.35"]
Two valid segmentations exist.
Example 2
Input
s = "0000"
Output
["0.0.0.0"]
Each part is a single zero.