Leetcode 93: Restore IP Addresses

1. Problem Summary

You’re given a string s consisting only of digits. You must insert three dots into s to form exactly four parts that make a valid IPv4 address:

Each part is an integer in [0, 255].
No leading zeros allowed, unless the part is exactly "0".

You must:

Use all digits in s in order (no reordering or deletion).
Return all possible valid IP addresses in any order.

Input: s (string of digits, 1 <= len(s) <= 20)

Output: List of strings, each a valid IPv4 address formed from s.

2. Examples Explanation

Example 1:

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

Possible splits into 4 segments that are in [0,255] and valid (no leading zeros):

255.255.11.135: all segments valid.
255.255.111.35: all segments valid.

Other splits either exceed 255 or create leading zeros.

Example 2:

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

Only possible valid segmentation:

0.0.0.0: each segment is "0", allowed with no leading zeros issue (single 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"]

Each returned string:

Has 4 parts.
Each part is within [0,255].
No part has leading zeros (e.g., "01" or "023" would be invalid).

3. Approach

Pattern:

This is a backtracking / DFS problem on a string with constrained segment lengths.

Naive Idea:

Generate all ways to place 3 dots in the string:

Choose positions i < j < k to split into s[0:i], s[i:j], s[j:k], s[k:].
Check each segment validity.

This is actually not too bad since segment length is at most 3, but implementing it via structured backtracking is clearer and naturally prunes invalid branches early.

4. Optimal Approach: Backtracking with Pruning

High-Level Idea:

We try to build the IP address segment by segment:

At each recursion step, we choose the next segment:

Length 1, 2, or 3 characters.

Validate the chosen segment:

If it starts with '0' and length > 1 → invalid.
Convert to integer; must be 0 <= val <= 255.

Recurse to build the remaining segments.
Stop when we have exactly 4 segments:

If we also consumed all characters in s, record a valid IP.
Otherwise discard.

We also prune using remaining length constraints.

Key Observations / Pruning:

Let:

index = current position in s
segments = number of segments chosen so far

We must end with exactly 4 segments.
Remaining characters: remaining = len(s) - index

Minimum characters needed = remainingSegments = 4 - segments (if each is length 1).
Maximum characters allowed = remainingSegments * 3 (if each is length 3).
If remaining < remainingSegments or remaining > remainingSegments * 3, we can prune.

When choosing segment length:

Try len = 1 to 3, but not beyond the end of the string.
If the first char is '0', only len = 1 is allowed.

This keeps the search small and efficient.

Pseudo-code:

Complexity Analysis:

Let n=len(s), and note n≤20.

Time Complexity:

At most 3 choices per segment, 4 segments → upper bound like O(34) per path, but heavily pruned.
In practice, it's a very small constant. Theoretical bound is O(1) wrt input limits, or more precisely O(n4) in a very loose worst-case, but for n≤20 This is fine.