93. Restore IP Addresses
mediumGiven a string of digits, return every valid IPv4 address you can form by inserting three dots. Classic substring-partition backtracking with realistic input validation — each segment must be 0-255 and have no leading zeros.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros. Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.
Constraints
1 <= s.length <= 20s consists of digits only.
Examples
Example 1
s = "25525511135"["255.255.11.135","255.255.111.35"]Example 2
s = "0000"["0.0.0.0"]Example 3
s = "101023"["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Recurse with (start index, segments collected so far).
Hint 2
Each segment is 1-3 characters. Loop length from 1 to 3 and slice s[start..start+length].
Hint 3
Validate: no leading zero unless segment is exactly '0'; numeric value 0..255.
Hint 4
Base case: segments.length == 4 AND start == s.length -> join with dots and append.
Solution approach
Reveal approach
Backtrack with (start, segments). Base case: segments.length == 4 -> if start == s.length, join segments with '.' and append to result; return either way. Otherwise loop len from 1 to 3, ensure start + len <= s.length, slice the candidate segment, validate (no leading zero unless segment == '0', integer value <= 255). If valid, push segment, recurse(start + len, segments), pop. Two important prune cases: stop loop early when len > 1 and first character is '0' (no leading-zero rule), and skip when the integer value is > 255. Time is O(1) in input size since s.length is capped — there are at most 3^4 = 81 partition tries. Space O(1).
Complexity
- Time
- O(1) — bounded by 3^4
- Space
- O(1)
Related patterns
- backtracking
- recursion
- string-partition
Related problems
- 131. Palindrome Partitioning
- 468. Validate IP Address
- 139. Word Break
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Microsoft
- Bloomberg
Practice these live with InterviewChamp.AI
Drill Restore IP Addresses and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →