What is the brute force approach and complexity for Restore IP Addresses?

Try all three-cut positions and check the four parts of each split with time complexity O(N⁴) and space complexity O(N).

What is the optimal approach and complexity for Restore IP Addresses?

Place one part at a time (1 to 3 digits); prune when the digits left cannot fill the parts left with optimal time complexity O(1) and space complexity O(1).

How do you identify the pattern for Restore IP Addresses?

Look for key signals in the prompt: "exactly four parts" indicates Exactly three cuts are needed, so the search always has depth 4.; "each part from 0 to 255" indicates A part is valid only when its value is small enough. Check it as soon as it is chosen.; "no leading zeros" indicates A part longer than one digit cannot start with 0. This removes choices before the search goes deeper.; "return all valid addresses" indicates Every valid split is an answer, so the search must reach every valid leaf, not just the first one..

Restore IP Addresses

Medium·LeetCode #93 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You are given a string s of digits. Insert dots into s to make valid IPv4 addresses. A valid address has exactly four parts. Each part is a number from 0 to 255, and it cannot have a leading zero: 01 is not allowed, but 0 is. You may not reorder or remove any digits. Return every address you can make, in any order.

Input

A string s of digits.

Output

A list of every valid address. Each address is the digits of s with three dots inserted.

Example 1

Input: s = "25525511135"

Output: [255.255.11.135, 255.255.111.35]

Both splits give four parts with values from 0 to 255 and no leading zeros: 255 | 255 | 11 | 135 and 255 | 255 | 111 | 35.

Example 2

Input: s = "0000"

Output: [0.0.0.0]

Every part is a single zero. A single zero is allowed, so there is one address.

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]

Five splits work. For example, 1 | 0 | 10 | 23 is valid, and so is 1 | 0 | 102 | 3, because 102 is at most 255.

Constraints

• 1 ≤ s.length ≤ 20
• `s` consists of digits only.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“exactly four parts”

→ Exactly three cuts are needed, so the search always has depth 4.

“each part from 0 to 255”

→ A part is valid only when its value is small enough. Check it as soon as it is chosen.

“no leading zeros”

→ A part longer than one digit cannot start with 0. This removes choices before the search goes deeper.

“return all valid addresses”

→ Every valid split is an answer, so the search must reach every valid leaf, not just the first one.

Approach Complexity Ladder

Brute Force — try every split into four partsO(N⁴)O(N)

Try all three-cut positions and check the four parts of each split

Optimal — backtrack over the four parts, prune impossible splitsO(1)O(1)

Place one part at a time (1 to 3 digits); prune when the digits left cannot fill the parts left

Brute Force Intuition

Choose three cut positions a < b < c. They split s into four parts: s[0..a), s[a..b), s[b..c) and s[c..]. Try every split into four parts, and keep the ones where all four parts are valid.

Recognition rule for this sub-pattern:

Cut the string at every valid position and recurse on the rest.

Remember this · Backtracking

Trigger

"All subsets / permutations / combinations", place items under rules (N-Queens, Sudoku), find a path in a grid.

Think

At each step, what are my choices, and how do I undo a choice?

Key question

What is my state, when is it complete, and when do I prune?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Backtracking translate into production architectures and low-level memory mechanics.

LLD Architecture