Skip to main content
DSA patterns

Restore IP Addresses

mediumStringsPalo Alto NetworksFortinetCisco

Problem statement

You're given a string s made only of digits. Insert three dots somewhere into it so the result is a valid IPv4 address — four numbers from 0 to 255, separated by dots, with no leading zeros (except the single digit "0" itself). You can't reorder or drop any digit; you can only decide where the dots go.

Return every valid IPv4 address you can build this way, in any order.

This is the reverse of the usual "validate an address" check: instead of confirming a well-formed string, you're reconstructing every well-formed string that a digit-only source (like a stripped log field or a malformed config value) could have come from.

Examples

Example 1

Input: s = "25525511135"

Output: ["255.255.11.135","255.255.111.35"]

Explanation: Two ways to place the dots keep every one of the four resulting numbers at 255 or below with no leading zero. For example, cutting after "255", "255", "11" gives 255.255.11.135.

Example 2

Input: s = "0000"

Output: ["0.0.0.0"]

Explanation: There's only one way to place the dots so every part is one digit — and a lone "0" is a valid (if unusual) IPv4 octet.

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: Several different dot placements all produce valid addresses, since the digits allow more than one way to group them into four numbers ≤ 255 with no leading zeros.

Hints

Hint 1: A valid IPv4 address always has exactly 3 dots, splitting the string into exactly 4 pieces — so the real question is just "where do the cuts go?"

Approach

Optimal: Backtracking with pruning

Intuition

Instead of building every possible 3-dot placement and checking it at the end (like the brute-force approach does), build the address one piece at a time and check each piece the moment it's chosen. If a piece is already invalid — too many digits left over, a leading zero, or a value over 255 — there's no point trying to finish that address at all, so stop immediately and try a different length for that piece. This is what makes it faster: bad choices are cut off at the root of their branch instead of being fully built out first.

Steps

  1. If s is shorter than 4 or longer than 12 characters, return an empty list immediately.
  2. Keep a running list of pieces chosen so far, and a starting index into s for the next piece.
  3. If 4 pieces have already been chosen: if every character of s has been used, join the pieces with dots and record that address; either way, stop this branch.
  4. Otherwise, prune early: if the characters left over can't possibly fill the remaining pieces (more than 3 × remaining pieces characters left), stop this branch — no combination of lengths 1–3 could use them all.
  5. Try taking the next piece as 1, then 2, then 3 characters. For each length, check the piece is valid (no leading zero unless it's "0", value ≤ 255); if it is, add it to the list and recurse from the new starting index.
  6. After a recursive call returns, remove the last piece (backtrack) so the next length can be tried cleanly.
  7. Once every combination has been explored, return the recorded addresses.

Dry run

s = "0000" — tracing the calls that actually build a result (the recursion also tries lengths 2 and 3 at each step, but those all fail the leading-zero rule immediately and aren't shown):

call start pieces so far piece tried valid? next
1 0 [] "0" yes recurse start=1
2 1 ["0"] "0" yes recurse start=2
3 2 ["0", "0"] "0" yes recurse start=3
4 3 ["0", "0", "0"] "0" yes recurse start=4
5 4 ["0", "0", "0", "0"] — 4 pieces, start == n join → "0.0.0.0"

At every step here, trying a 2- or 3-character piece instead (like "00") fails the leading-zero check right away and is abandoned without any further recursion — that's the pruning at work.

Edge cases: a string outside the 4–12 length range never starts the recursion. A string with no valid split at all (like "9999999999999", too long) still terminates quickly because the length check runs first.

Complexity

Time O(1) - amortized — At each of the 4 pieces the code only ever tries 3 possible lengths, so the whole search tree has at most 3⁴ = 81 leaves regardless of how long `s` is; a bad choice is abandoned the instant it's made, so most branches stop long before reaching that depth.

Space O(1) - extra — Beyond the output list, the only extra memory is the current 4-piece-deep recursion stack and the small list of pieces built so far.

class Solution:
    def restoreIpAddresses(self, s: str) -> list[str]:
        n = len(s)
        result: list[str] = []
        if n < 4 or n > 12:
            return result
        segments: list[str] = []

        def backtrack(start: int) -> None:
            if len(segments) == 4:
                if start == n:
                    result.append(".".join(segments))
                return
            remaining_segments = 4 - len(segments)
            remaining_chars = n - start
            if remaining_chars > remaining_segments * 3:
                return
            for length in range(1, 4):
                if start + length > n:
                    break
                part = s[start:start + length]
                if not self._is_valid_segment(part):
                    continue
                segments.append(part)
                backtrack(start + length)
                segments.pop()

        backtrack(0)
        return result

    def _is_valid_segment(self, part: str) -> bool:
        if len(part) > 1 and part[0] == "0":
            return False
        return int(part) <= 255


if __name__ == "__main__":
    s = Solution()
    print(s.restoreIpAddresses("25525511135"))  # ['255.255.11.135', '255.255.111.35']
    print(s.restoreIpAddresses("0000"))  # ['0.0.0.0']
    print(s.restoreIpAddresses("101023"))  # ['1.0.10.23', '1.0.102.3', '10.1.0.23', '10.10.2.3', '101.0.2.3']
RecapThe whole problem in a few lines, for the night before
  • Spot it: split a digit string into 4 valid IP parts in every possible way
  • Idea: backtracking: choose 1 to 3 digits for each part, check it is 0 to 255 with no leading zero, and stop when 4 parts use all the digits
  • Cost: O(1) time and space in practice (at most 3^4 splits of at most 12 digits)
  • Trap: "0" is valid but "01" or "00" is not; and all digits must be used

Interview follow-ups

  • What if addresses could be IPv6, using hex digits instead of only 0–9?

    The same backtracking shape applies with different constants: instead of 4 pieces of at most 3 digits, you'd build 8 pieces of at most 4 hex characters each, and the validity check would allow 0–9, a–f, A–F instead of checking a numeric range. The pruning rule (remaining characters can't exceed remaining pieces × max length) works exactly the same way with the new numbers plugged in.

  • Does the order of the results matter, or could it be different from the examples?

    The problem allows any order, but this backtracking approach naturally produces them in the order you'd read s left to right, trying 1-digit pieces before 2-digit before 3-digit at each position — which is why it matches the example outputs exactly. If a specific order (say, lexicographic) were required instead, collect all the addresses first and sort the final list, which costs an extra O(k log k) for k results.

  • The input can be extremely long (millions of digits), but you only need a count of valid addresses, not the list itself.

    The length check at the very start already handles this well: anything outside 4–12 characters returns immediately without any recursion, so an absurdly long string is rejected in O(1) time regardless of its length. If counting mattered for strings that do fall in that small range, you could still return a count instead of a list by incrementing a counter at the base case instead of building a string — same time complexity, but without paying to allocate and store the joined strings.

Frequently asked questions

Because 255 is the largest legal IPv4 octet, and 255 is the largest 3-digit number that qualifies — anything with 4 or more digits (like "1000") is automatically too big, so there's never a reason to try a longer piece.

"01" and "1" represent the same number, but a real IPv4 address never writes it with the extra zero — some tools historically read a leading-zero number as octal, so allowing it invites ambiguity. The single character "0" is the one exception, since there's no shorter way to write zero.

Both explore a bounded amount of work in the worst case, so on the tiny inputs this problem allows (at most 12 characters) the difference is small in practice. The real benefit shows up on the near-misses: a string like "999999999999" has every possible first cut fail immediately (every 3-digit prefix is over 255), so backtracking abandons the whole search after trying just 3 pieces, while the brute-force version still has to build and check every one of its C(11, 3) = 165 candidate splits before it can conclude there are no answers.

Reconstructing a structured value — an address, a version string, a serial number — from a raw stream of characters comes up when a delimiter has been stripped by an upstream system, or when parsing a fixed-format legacy log field character by character. The same "try each valid length, backtrack on failure" shape applies any time you're splitting a string into pieces that each have their own validity rule.

Not really. DP shines when overlapping subproblems get solved repeatedly — but here the search tree is already tiny and bounded (at most 81 leaves, since there are only 4 pieces and 3 choices at each), so there's nothing expensive to save by memoising. Backtracking with the early-exit pruning shown here does the same amount of essential work with much simpler code.