Log inSign up
mediumLeetCodeNot Started

Restore IP Addresses

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on LeetCode
Lesson

Problem Statement

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 (unless the integer is 0 itself).

- 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"]
Explanation: Both segmentations yield 4 valid octets in range [0, 255] without leading zeroes.

Example 2:

Input: s = "0000"
Output: ["0.0.0.0"]
Explanation: Only one way to place dots such that each octet is "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"]
Explanation: 5 valid IPv4 segmentations can be formed.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master lookahead capacity constraints in fixed-depth backtracking.
  • Correctly implement numerical boundary parsing and leading zero guards in string recursion.
  • Recognize when recursive backtracking has constant upper-bounded complexity O(1).

1. Triple Nested Loops for 3 Dot Placements

Intuition

Iterate i from 1 to 3, j from i+1 to i+3, and k from j+1 to j+3. Slice the 4 segments s[0..i], s[i..j], s[j..k], s[k..N], and check if all 4 are valid.

Algorithm

  1. Step 1: Use 3 nested loops to place 3 dot separators dividing string into 4 parts.
  2. Step 2: For each split (s1, s2, s3, s4), check length constraints (1 to 3 characters each).
  3. Step 3: Validate each segment: no leading zeros (unless single 0) and numeric value <= 255.
  4. Step 4: If all 4 segments are valid, format as s1.s2.s3.s4 and add to result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5class Solution {
6public:
7 bool isValid(const std::string& s) {
8 if (s.empty() || s.length() > 3) return false;
9 if (s[0] == '0' && s.length() > 1) return false;
10 int val = std::stoi(s);
11 return val >= 0 && val <= 255;
12 }
13
14 std::vector<std::string> restoreIpAddresses(std::string s) {
15 std::vector<std::string> result;
16 int n = s.length();
17 if (n < 4 || n > 12) return result;
18
19 for (int i = 1; i <= 3 && i < n; i++) {
20 for (int j = i + 1; j <= i + 3 && j < n; j++) {
21 for (int k = j + 1; k <= j + 3 && k < n; k++) {
22 std::string s1 = s.substr(0, i);
23 std::string s2 = s.substr(i, j - i);
24 std::string s3 = s.substr(j, k - j);
25 std::string s4 = s.substr(k);
26
27 if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) {
28 result.push_back(s1 + "." + s2 + "." + s3 + "." + s4);
29 }
30 }
31 }
32 }
33 return result;
34 }
35};
36
37int main() {
38 Solution solver;
39 std::vector<std::string> res = solver.restoreIpAddresses("25525511135");
40 std::cout << "Nested Loop Output for '25525511135':\n";
41 for (const auto& ip : res) {
42 std::cout << ip << "\n";
43 }
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(1) — Loops execute at most 3 * 3 * 3 = 27 iterations.
  • Space complexity: O(1) — O(1) auxiliary memory.

2. Standard DFS Backtracking

Intuition

Recurse with path tracking the current segments. When path.length == 4, check if all string characters were consumed. Branch for segment lengths 1, 2, and 3.

Algorithm

  1. Step 1: Define backtrack(start, segmentCount, currentSegments).
  2. Step 2: Base case: if segmentCount == 4 and start == s.length, join segments with . and add to result.
  3. Step 3: Loop length len from 1 to 3.
  4. Step 4: Extract sub = s.substring(start, start + len).
  5. Step 5: Validate: if len > 1 && sub[0] == 0 break; if parseInt(sub) > 255 break.
  6. Step 6: Push sub, recurse on backtrack(start + len, segmentCount + 1), and pop.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5class Solution {
6public:
7 void backtrack(const std::string& s, int start, std::vector<std::string>& path, std::vector<std::string>& result) {
8 if (path.size() == 4) {
9 if (start == (int)s.length()) {
10 result.push_back(path[0] + "." + path[1] + "." + path[2] + "." + path[3]);
11 }
12 return;
13 }
14
15 for (int len = 1; len <= 3 && start + len <= (int)s.length(); len++) {
16 std::string segment = s.substr(start, len);
17 if (segment.length() > 1 && segment[0] == '0') break;
18 int val = std::stoi(segment);
19 if (val > 255) break;
20
21 path.push_back(segment);
22 backtrack(s, start + len, path, result);
23 path.pop_back();
24 }
25 }
26
27 std::vector<std::string> restoreIpAddresses(std::string s) {
28 std::vector<std::string> result;
29 if (s.length() < 4 || s.length() > 12) return result;
30 std::vector<std::string> path;
31 backtrack(s, 0, path, result);
32 return result;
33 }
34};
35
36int main() {
37 Solution solver;
38 std::vector<std::string> res = solver.restoreIpAddresses("25525511135");
39 std::cout << "DFS Output for '25525511135':\n";
40 for (const auto& ip : res) {
41 std::cout << ip << "\n";
42 }
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(1) bounded by 3^4 = 81 calls — Maximum 81 recursive leaf checks.
  • Space complexity: O(1) recursion depth 4 — Recursion depth is fixed at 4.

3. DFS with Lookahead Capacity Pruning

Intuition

If remaining characters are fewer than remaining segments needed, or exceed 3 times remaining segments, prune the branch immediately before creating strings or parsing numbers.

When to apply: Industry standard optimal solution: O(1) bound checking with aggressive length pruning.

Algorithm

  1. Step 1: Early pruning: If s.length < 4 or s.length > 12, return empty list immediately.
  2. Step 2: In backtrack(start, segments): check remaining character bounds: if remaining < (4 - segments) or remaining > (4 - segments) * 3, prune branch.
  3. Step 3: Try segment lengths 1, 2, 3 starting at start index.
  4. Step 4: Reject invalid numbers (> 255) and numbers with leading zeros in O(1).
  5. Step 5: Recurse on valid segments; backtrack state upon return.
  6. Step 6: Collect all valid IPv4 dot-decimal representations.

IPv4 Segment Backtracking Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Start at index 0 with 0 segments formed
Visual state
Values and pointers at this exact step
tree
Start
seg: 0, s: '25525511135'

Node order shown; add connections to display explicit tree edges.

Variables at this step
start
0
segments
0
current
[]
Check / comparison
start = 0, segments = 0, s = '25525511135'
Decision / next transition
Explore candidate lengths 1, 2, 3 for Segment 1
Why this step matters

Start at index 0 with 0 segments formed. Remaining length 11 is valid (4 <= len <= 12).

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5class Solution {
6public:
7 void backtrack(const std::string& s, int start, int segmentCount, std::string currentIp, std::vector<std::string>& result) {
8 int remChars = (int)s.length() - start;
9 int remSegments = 4 - segmentCount;
10
11 // Lookahead boundary pruning
12 if (remChars < remSegments || remChars > remSegments * 3) return;
13
14 if (segmentCount == 4) {
15 if (start == (int)s.length()) {
16 currentIp.pop_back(); // Remove trailing dot
17 result.push_back(currentIp);
18 }
19 return;
20 }
21
22 int val = 0;
23 for (int i = start; i < start + 3 && i < (int)s.length(); i++) {
24 if (i > start && s[start] == '0') break;
25 val = val * 10 + (s[i] - '0');
26 if (val > 255) break;
27
28 backtrack(s, i + 1, segmentCount + 1, currentIp + s.substr(start, i - start + 1) + ".", result);
29 }
30 }
31
32 std::vector<std::string> restoreIpAddresses(std::string s) {
33 std::vector<std::string> result;
34 if (s.length() < 4 || s.length() > 12) return result;
35 backtrack(s, 0, 0, "", result);
36 return result;
37 }
38};
39
40int main() {
41 Solution solver;
42 std::vector<std::string> res = solver.restoreIpAddresses("25525511135");
43 std::cout << "Optimal Pruned Output for '25525511135':\n";
44 for (const auto& ip : res) {
45 std::cout << ip << "\n";
46 }
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(1) bounded by strictly minimal state space — Runs in constant O(1) time bounded by at most 81 evaluations.
  • Space complexity: O(1) recursion depth 4 — O(1) recursion stack space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.3-Nested Loops (Iterative Brute Force)O(1) (at most 27 iterations)O(1)Not extensible if the number of segments is variable.
2.Standard DFS Backtracking (Better)O(1) (at most 81 states)O(1)May explore branches where remaining length is impossible.
3.DFS with Lookahead Capacity Pruning (Optimal)OptimalO(1) (minimal states visited)O(1)Requires remainder length math check.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Allowing leading zeroes in multi-digit segments (e.g. treating 01 as valid 1). If a segment has length > 1, it must not start with 0.

Pitfall 2:

Allowing values greater than 255 (e.g. 256.100.1.1). Ensure integer conversion value val <= 255 is strictly checked.

Crucial Edge Cases to Validate:

  • String length < 4 or > 12: immediately return [].
  • String with all zeroes (e.g. 0000) -> returns [0.0.0.0].
  • String with leading zeroes in segments (e.g. 010010) -> correctly avoids segments like 01.
  • Max values (e.g. 25525511135) -> accurately bounds octets <= 255.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the initial length guard 4 <= s.length() <= 12 immediately.
  2. Explain both leading zero rules and 255 value limits before writing code.
  3. Discuss the lookahead pruning optimization remChars <= remSegments * 3 to demonstrate awareness of performance boundaries.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the time complexity of Restore IP Addresses considered O(1)?

Back to DSA Sheet