Is Restore IP Addresses easy or hard?

Restore IP Addresses is classified as a Medium difficulty problem. The challenge comes from correctly handling constraints such as leading zeros, segment bounds (0–255), and ensuring exactly four segments while exploring combinations efficiently.

Restore IP Addresses Python/Java solution

Python and Java implementations usually follow the backtracking pattern. The function recursively chooses segment lengths from 1 to 3, validates each substring, and appends valid segments to a list. Once four segments are formed and the string is consumed, they are joined with dots to produce a valid IP address.

How to solve Restore IP Addresses in O(n)?

A true O(n) solution is not practical because the algorithm must check multiple combinations of segment boundaries. The closest practical complexity is O(n^3), achieved using backtracking or enumerating split indices. The constraints on segment length keep the actual runtime small in practice.

What is the best approach for Restore IP Addresses?

Backtracking is the most common and interview-friendly approach. It builds the IP address one segment at a time and prunes invalid segments early using constraints like value ≤255 and no leading zeros. Because an IP address has exactly four segments with maximum length three, the search space remains small and manageable.

Is Restore IP Addresses asked at Google/Amazon/Meta?

Restore IP Addresses is a common medium-level backtracking problem and appears frequently in interview preparation lists for companies like Amazon, Google, and Meta. It tests string manipulation, constraint validation, and recursive search techniques.

What data structure is used in Restore IP Addresses?

The core structure is a list or array used to store the current segments while building the IP address. The algorithm also relies on recursion (backtracking) or loop indices to explore possible splits, along with basic string slicing for segment validation.

What is the time complexity of Restore IP Addresses?

The typical complexity is O(n^3). Each segment can have length 1–3 and there are four segments, so the algorithm explores combinations of split positions while validating segments. The recursion depth never exceeds four, so the auxiliary space is O(1) excluding the output list.

Description Solution Video 17:44

93. Restore IP Addresses

Medium57.3% acceptance20 companies

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.

For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

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.

Example 1:

Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]

Example 2:

Input: s = "0000"
Output: ["0.0.0.0"]

Example 3:

Input: s = "101023"
Output: ["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.

Asked at 20 companies

Arista Networks NVIDIA Hashedin Yahoo Motive Adobe Visa Bytedance Palo Alto Networks Wells Fargo Zopsmart Microsoft

+8 more

Tiktok Oracle Zoho

Google Amazon Meta Bloomberg Goldman Sachs

Topics

Backtracking String

17:44

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

93. Restore IP Addresses

Asked at 20 companies

Topics

Similar problems