Restore IP Addresses
Medium · Backtracking · String · Backtracking
Problem
A valid IPv4 address is four integers separated by single dots, where each integer is between 0 and 255 and has no leading zeros (so 0 is fine but 01 is not).
Given a string s of digits, return every valid IP address that can be formed by inserting exactly three dots into s. You may not reorder or delete any digits. The addresses may be returned in any order.
Examples
Input: s = "10203" Output: ["1.0.20.3","10.2.0.3"]
Splits such as 1.0.2.03 are rejected because 03 has a leading zero.
Input: s = "0000" Output: ["0.0.0.0"]
Each part must be a single 0.
Input: s = "1111111111111" Output: []
Thirteen digits cannot fit into four parts of at most three digits each.
Constraints
- 1 <= len(s) <= 20
- s consists only of digits
Approaches
- Try every placement of the three dots — time O(n³), space O(1) beyond the output
Follow-up
To count the splits of a long digit string into k parts up to some limit, listing them is hopeless; a DP over (digits used, parts made) counts them in O(n · k · L) for parts of up to L digits.
Related problems
Start free on Cariara · Coding problems · System design studio
