93. Restore IP Addresses - Detailed Explanation

Problem Statement

Given a string s containing only digits, your task is to return all possible valid IP address combinations that can be formed by inserting three dots into s.

An IP address consists of four parts (called octets) separated by dots. Each octet must meet the following criteria:

• It is a number between 0 and 255.
• It cannot have leading zeros (except the number 0 itself). For example, "01" or "00" is not valid.

Task:
Return all possible valid IP addresses that can be obtained from s.

Example 1:

• Input: s = "25525511135"
• Output: ["255.255.11.135", "255.255.111.35"]
• Explanation:
  The string "25525511135" can be split as:
  • "255", "255", "11", "135" → forms "255.255.11.135"
  • "255", "255", "111", "35" → forms "255.255.111.35"

Example 2:

• Input: s = "0000"
• Output: ["0.0.0.0"]
• Explanation:
  Each octet "0" is valid. Note that "00" or "000" are not allowed.

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:

• The input string contains only digits.
• The length of s is between 0 and 20, but valid IP addresses can only be formed if the length is between 4 and 12.

Hints

1. Backtracking/DFS:
   Think about placing three dots in the string. You need to choose three positions that divide the string into four segments. A recursive or backtracking approach allows you to try all possible splits and then backtrack if the current segmentation is invalid.

2. Segment Validation:
   Each segment should represent a valid integer in the range 0–255. Moreover, if a segment has more than one digit, it must not start with '0'. Write a helper function to validate segments.

3. Pruning Invalid Splits:
   Since an IP address must have exactly 4 segments and each segment is at most 3 characters long, you can limit the range for each split. For instance, if the remaining part of the string is too long or too short to form the remaining segments, you can stop exploring that branch.

Approaches to Solve the Problem

Approach 1: Backtracking / Depth-First Search (DFS)

Idea:

• Recursively try every possible split of the string into 4 parts.
• At each recursion level, choose a segment (up to 3 digits) if it is valid.
• Once 4 segments are formed and the entire string is used, add the IP address to the result.

Steps:

1. Define a helper function that takes the current position, the path (list of chosen segments), and the result list.
2. If 4 segments are chosen and the position equals the string length, join the segments with dots and add to results.
3. If the number of segments is 4 but there are still digits left (or vice versa), backtrack.
4. For each segment, check if it is valid:
   • It should not be longer than 3 characters.
   • Convert the segment to an integer; it must be between 0 and 255.
   • If the segment has more than one digit, it should not start with '0'.

Complexity:

• Time Complexity: O(1) in practice because the maximum length of s is 12 (fixed upper bound). In theoretical terms, it is exponential with respect to the number of segments, but here the constant factors make it manageable.
• Space Complexity: O(1) extra space (aside from recursion stack and the output list).

4. Step-by-Step Walkthrough

Consider s = "25525511135":

1. First Segment:
   • Try "2", "25", "255" (all valid segments).
2. Recursive Calls:
   For each chosen first segment, proceed to choose the second segment from the remaining string.
   • If first segment is "255", remaining string is "25511135".
3. Continue Splitting:
   For the second segment "255", remaining string is "11135". Then choose third and fourth segments similarly.
4. Validation:
   When a full IP (4 segments) is formed, validate that the entire string is consumed and the segments are valid.
5. Backtracking:
   If any branch does not lead to a valid IP address, backtrack and try a different segmentation.

The process will eventually list all valid combinations such as "255.255.11.135" and "255.255.111.35".

Code Implementation

Python Code