Problem Statement in English

You’re given a string s containing only digits. You need to return all possible valid IP addresses that can be formed by inserting dots into s. A valid IP address consists of four segments, each ranging from 0 to 255, and cannot have leading zeros (except for the number 0 itself).

Approach

We use backtracking to generate all possible combinations of IP address segments. At each step, we try to form a new segment by including the current character, ensuring it’s a valid segment (0-255) and doesn’t have leading zeros (except for “0” itself). We continue this process until we’ve processed the entire string and formed exactly four segments.

If we reach a buffer length of 4 and have consumed all characters in the string, we join the segments with dots and add the resulting IP address to our results list.

After each recursive call, we backtrack by removing the last segment added to the buffer, or reverting it to its previous state, allowing us to explore other combinations.

If the length of the buffer exceeds 4 or if we reach the end of the string without forming exactly 4 segments, we return early to avoid unnecessary computations. This is part of the rules provided in the problem statement.

And we’re done!

Solution in Python


class Solution:
    def restoreIpAddresses(self, s: str) -> list[str]:
        N = len(s)
        buffer = []
        res = []

        def dfs(i):
            if i == N:
                if len(buffer) == 4:
                    res.append(".".join(buffer))
                return

            if buffer:
                current_seg = buffer[-1]
                if current_seg != "0":
                    updated = current_seg + s[i]
                    if int(updated) <= 255:
                        buffer[-1] = updated
                        dfs(i + 1)
                        buffer[-1] = current_seg

            if len(buffer) < 4:
                buffer.append(s[i])
                dfs(i + 1)
                buffer.pop()

        dfs(0)
        return res

Complexity

  • Time: $O(2^N)$
    This is because at each character, we have two choices: either to extend the current segment or to start a new segment. In the worst case, this leads to an exponential number of combinations.

  • Space: $O(n)$
    Since we use a buffer to store the current segments, and the maximum depth of recursion is limited by the length of the string.

And we are done.