DSA problem
Restore IP Addresses
Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting exactly three dots into s. You are not allowed to reorder or remove any digits in s. Each of the four numeric segments separated by dots must be in [0, 255] and may not contain leading zeros (so "0" is allowed but "01" is not).
This problem is a constrained string partition: we need to split s into exactly four non-empty contiguous segments such that each segment satisfies the IP-segment rule. Brute force would try every (i, j, k) triple of dot positions and check validity, giving roughly C(n - 1, 3) partitions; backtracking arrives at the same answer with cleaner pruning baked in.
The recursive routine maintains a list of segments built so far and a start index into s. At each call we have one of four states (segments.length == 0..3) and need to pick the length of the next segment (1, 2, or 3 digits). We validate immediately: a 2 or 3-digit segment cannot start with '0', and a 3-digit segment value must be <= 255. Pre-pruning these cases avoids descending into impossible branches.
When segments.length == 4, we have four segments; if start == s.length we have consumed the whole string and can join with dots to produce a valid IP address. Otherwise we discard the path. With n <= 12 digits and at most 3 choices per slot, total work is bounded by 3^4 = 81 paths — tiny.
Examples
s = "25525511135"["255.255.11.135","255.255.111.35"]s = "0000"["0.0.0.0"]s = "101023"["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]Constraints
- 1 <= s.length <= 20
- s consists of digits only.
- Each segment of a valid IP address is a decimal integer in [0, 255].
- Segments may not contain leading zeros except for the value 0 itself.
- Exactly three dots must be inserted to form four segments.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.