MediumStringBacktrackingUpdated Sep 2026

93. Restore IP Addresses

Asked at Oracle, NVIDIA

Difficulty

Medium

Time

O(1) in practice (at most 3^4 =

Space

O(1) extra besides the output (r

Pattern

String

Companies

2

Problem

You are given a string s that contains only digits. Your job is to put three dots into it so that it becomes a valid IP address, and return all such addresses.

A valid IP address has exactly four parts separated by single dots. Each part is a number from 0 to 255. A part may not have leading zeros, so "0" is fine but "01" and "011" are not. You must keep the digits in their original order — you can only insert dots, never move or delete digits.

Return the list of all valid addresses. The order of the answers does not matter. If no valid address exists, return an empty list.

Cut the digits into four parts

s2552551113525525511135012345678910One valid split: 255.255.11.135 — each bracket is one part of the address.part must be 0..255no leading zeros: "01" is badorder of digits never changes
We must place three dots so the string splits into four parts, each a number from 0 to 255 with no leading zeros.

Constraints

  • ●1 <= s.length <= 20
  • ●s consists of digits only

Examples

Example 1
Inputs = "25525511135"
Output["255.255.11.135","255.255.111.35"]
WhyThere are only two ways to cut this string into four valid parts. One is 255 | 255 | 11 | 135, the other is 255 | 255 | 111 | 35. Every other split makes a part that is too big or has a leading zero.
Example 2
Inputs = "0000"
Output["0.0.0.0"]
WhyEach part must be exactly one digit here, because a part like "00" has a leading zero. So the only split is 0 | 0 | 0 | 0.
Example 3
Inputs = "101023"
Output["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
WhyThe string has 6 digits, so the four parts must have lengths that add up to 6, like 1+1+2+2 or 1+1+3+1. Each of these five splits gives four parts that are all between 0 and 255 with no leading zeros.

Asked At

2 companies
CompanyDifficulty
OracleMediumView all Oracle questions →
NVIDIAMediumView all NVIDIA questions →

How to Think About It

1

Brute force: try every possible way to split s into 4 non-empty parts.

2

Use backtracking to build each octet one at a time.

3

Prune branches where the current octet exceeds 255 or has leading zeros.

4

At each step, try taking 1, 2, or 3 characters for the current octet.

5

When 4 octets are formed and all of s is consumed, add the result.

Optimal Approach

Use backtracking to try placing 1, 2, or 3 digits for each of the four octets. At each step, extract the substring, validate it (no leading zeros, value 0-255), and recurse for the next octet. When four valid octets are placed and no characters remain, add the IP to the result. The maximum recursion depth is 4 and each level branches at most 3 ways, giving O(1) effective time with string operations dominating at O(n).

Backtracking: pick 1, 2 or 3 digits per part

start at index 0, parts = []take 1, 2 or 3 digitsreject if >255 or leading zerorecurse for next part4 parts and end of s → saveThe whole algorithm is this loop, repeated until four parts are placed.s255 ok255 ok111 ok35 ok25525511135012345678910A second branch: 255 | 255 | 111 | 35, which is the other valid answer.if len(part) > 1 and part[0] == '0': stopif int(part) > 255: stopif parts == 4 and start == len(s): save
At each of the four steps we take a short prefix, check it, and recurse; bad prefixes stop that branch.
ComplexityTime O(1) in practice (at most 3^4 = Space O(1) extra besides the output (rThe search tree is tiny and fixed: four levels, each trying at most three part lengths, so the cost is dominated by building the answer strings.

What Trips People Up in Real Interviews

1

Clarify edge cases: leading zeros (only "0" is valid), empty segments.

2

Mention pruning strategies to avoid unnecessary recursion.

3

Explain why at most 3 digits per octet bounds the recursion.

4

Discuss that the result set is small so backtracking is efficient.

5

Ask if duplicates need to be handled (input guarantees no ambiguity).

Solution Code

O(1) in practice (at most 3^4 = time
def restoreIpAddresses(s):
    result = []
    def backtrack(start, parts):
        if len(parts) == 4:
            if start == len(s):
                result.append('.'.join(parts))
            return
        for length in range(1, 4):
            if start + length > len(s):
                break
            segment = s[start:start + length]
            if len(segment) > 1 and segment[0] == '0':
                break
            if int(segment) > 255:
                break
            backtrack(start + length, parts + [segment])
    backtrack(0, [])
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Restore IP Addresses problem?

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. A valid IP address consists of exactly four integers separated by single dots, where each integer is between 0 and 255.

How do you solve Restore IP Addresses?

The optimal approach runs in O(1) in practice (at most 3^4 = time and O(1) extra besides the output (r space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Restore IP Addresses?

Restore IP Addresses is asked at Oracle, NVIDIA. It is a medium difficulty problem.

What are common mistakes on Restore IP Addresses?
  • Clarify edge cases: leading zeros (only "0" is valid), empty segments.
  • Mention pruning strategies to avoid unnecessary recursion.
  • Explain why at most 3 digits per octet bounds the recursion.
  • Discuss that the result set is small so backtracking is efficient.
  • Ask if duplicates need to be handled (input guarantees no ambiguity).