#93

Medium

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Restore IP Addresses

Restore all valid IP addresses from a string using backtracking with pruning, avoiding invalid segments or leading zeros.

string backtracking

Problem Statement

Given a string s containing only digits, generate all possible valid IP addresses by inserting three dots to split it into four integers. Each integer must be between 0 and 255 inclusive and cannot have leading zeros. You must preserve the original order of digits and cannot remove any character.

Return all valid IP addresses in any order. For example, given s = "25525511135", the valid outputs are ["255.255.11.135","255.255.111.35"]. The string length is at least 1 and at most 20.

Examples

Example 1

Input: s = "25525511135"

Output: ["255.255.11.135","255.255.111.35"]

Example details omitted.

Example 2

Input: s = "0000"

Output: ["0.0.0.0"]

Example details omitted.

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"]

Example details omitted.

Constraints

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

Solution Approach

Use Backtracking with Pruning

Start from the first character and recursively try to place dots after 1 to 3 digits. If a segment exceeds 255 or has leading zeros, prune that path immediately to avoid invalid addresses.

Track Current Segments and Position

Maintain a list of current segments and the current index in the string. When four segments are formed, check if the entire string has been consumed to validate a complete IP address.

Aggregate Valid Addresses

Once a valid combination of four segments is found, join them with dots and add to the result list. Continue backtracking to explore other possibilities until all options are exhausted.

Complexity Analysis

Metric	Value
Time	O(M ^ N \cdot N)
Space	O(M \cdot N)

Time complexity is O(M ^ N \cdot N), where M is the maximum segment length (3) and N is the string length, due to recursive exploration. Space complexity is O(M \cdot N) for the recursion stack and temporary segment storage.

What Interviewers Usually Probe

Expect candidates to handle leading zeros correctly and prune invalid paths.
Look for efficient recursive or iterative backtracking rather than brute-force splitting.
Watch if candidate avoids unnecessary string copying and joins segments carefully.

Common Pitfalls or Variants

Common pitfalls

Not pruning segments larger than 255 leads to TLE.
Allowing leading zeros in multi-digit segments generates invalid addresses.
Incorrectly handling string bounds when placing dots can cause out-of-range errors.

Follow-up variants

Return only the first k valid IP addresses instead of all.
Count the total number of valid IP addresses without listing them.
Generate IP addresses for a string that may contain non-digit separators, ignoring them in validation.

FAQ

What is the best approach to solve Restore IP Addresses?

Use backtracking with pruning, trying segments of length 1 to 3 and discarding invalid ones immediately.

How do you handle leading zeros in Restore IP Addresses?

A segment with multiple digits cannot start with '0'; only single-digit '0' is valid.

What is the time complexity for this problem?

The time complexity is O(M ^ N \cdot N) due to recursive exploration of segments, with M being 3 and N the string length.

Can this problem be solved iteratively instead of recursively?

Yes, but iterative solutions typically simulate the backtracking process with explicit stacks, which can be more complex.

Why is pruning important in Restore IP Addresses?

Pruning prevents exploring invalid segments, reducing unnecessary recursion and improving efficiency.

terminal

Solution

Solution 1: DFS

We define a function $dfs(i)$, which represents the list of IP addresses that can be formed starting from the $i$th position of string $s$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def check(i: int, j: int) -> int:
            if s[i] == "0" and i != j:
                return False
            return 0 <= int(s[i : j + 1]) <= 255

        def dfs(i: int):
            if i >= n and len(t) == 4:
                ans.append(".".join(t))
                return
            if i >= n or len(t) >= 4:
                return
            for j in range(i, min(i + 3, n)):
                if check(i, j):
                    t.append(s[i : j + 1])
                    dfs(j + 1)
                    t.pop()

        n = len(s)
        ans = []
        t = []
        dfs(0)
        return ans

Continue Practicing

#79 word search #126 word ladder ii #131 palindrome partitioning