A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

  • For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You may not reorder or remove any digits in s. You may return the valid IP addresses in any order.

Examples

Example 1:

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

Example 2:

Input: s = "0000"
Output: ["0.0.0.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"]

Constraints

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

Thinking Process

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

  • For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

  • Build solution incrementally; undo (backtrack) when constraints fail.
  • Prune branches early to avoid exploring invalid partial states.
  • Sort input to skip duplicate combinations efficiently.
Backtracking tree start choose → explore → undo (prune)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Choose / explore / unchoose (this problem) O(2^n) O(n) Subsets, combinations
Constraint pruning Reduced search O(n) Early exit on invalid partial
Sort + skip duplicates O(2^n) O(n) Combination sum II style
Path recording O(n!) worst O(n) Permutations

Solution

Time Complexity: O(1) - At most 3^4 = 81 combinations
Space Complexity: O(1) - At most 19 characters per IP address

This solution uses backtracking to try all possible ways to split the string into 4 parts. We optimize with Python20 features including string_view for efficient substring operations and early pruning.

Solution 1: Optimized Python20 Version

using namespace std
class Solution:
# Check if a segment is valid using string_view for efficiency
def isValid(self, segment):
    len = segment.length()
    # Single digit is always valid (0-9)
    if (len == 1) return True
    # Leading zero is invalid
    if (segment[0] == '0') return False
    # Check if <= 255 using efficient comparison
    if (len == 2) return True  // 10-99
    if len == 3:
        # Compare with "255" lexicographically
        return segment <= "255"
    return False  # len > 3 is invalid
void backtrack(
string_view s,
start,
list[int> dots,
list[str> result
) :
remainingLen = (int)s.length() - start
remainingCnt = 4 - (int)len(dots)
# Early pruning: check if remaining digits can form valid segments
if remainingLen > remainingCnt * 3  or  remainingLen < remainingCnt:
    return
# Base case: we have 3 dots, check if remaining segment is valid
if len(dots) == 3:
    lastSegment = s.substr(start)
    if isValid(lastSegment):
        # Build IP address efficiently
        str ip
        ip.reserve(s.length() + 3)  # Reserve space for dots
        last = 0
        for dot in dots:
            ip.append(s.substr(last, dot))
            last += dot
            ip.append(".")
        ip.append(s.substr(start))
        result.append(move(ip))
    return
# Try segments of length 1, 2, or 3
for (curr = 1 curr <= 3  and  curr <= remainingLen curr += 1) :
dots.append(curr)
segment = s.substr(start, curr)
if isValid(segment):
    backtrack(s, start + curr, dots, result)
dots.pop()
def restoreIpAddresses(self, s):
    list[int> dots
    dots.reserve(3)  # At most 3 dots
    list[str> result
    # Use string_view to avoid copying
    string_view sv(s)
    backtrack(sv, 0, dots, result)
    return result

Solution Explanation

Approach: Choose / explore / unchoose (this problem)

Key idea: A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

How the code works:

  • For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.
  • Build solution incrementally; undo (backtrack) when constraints fail.
  • Prune branches early to avoid exploring invalid partial states.
  • Sort input to skip duplicate combinations efficiently.

Walkthrough — input s = "25525511135", expected output ["255.255.11.135","255.255.111.35"]:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.
Aspect Complexity
Time O(1) - At most 3^4 = 81 combinations
Space O(1) - At most 19 characters per IP address
Recursion Depth O(4) - Maximum 4 segments

Solution 2: Further Optimized with String Building

class Solution:
    def isValid(self, segment):
        length = len(segment)

        if length == 1:
            return True

        if segment[0] == '0':
            return False

        if length == 2:
            return True

        return length == 3 and int(segment) <= 255

    def backtrack(self, s, start, segments, result):
        remainingLen = len(s) - start
        remainingCnt = 4 - len(segments)

        if remainingLen > remainingCnt * 3 or remainingLen < remainingCnt:
            return

        if len(segments) == 3:
            lastSegment = s[start:]

            if self.isValid(lastSegment):
                ip = ""
                pos = 0

                for segLen in segments:
                    ip += s[pos:pos + segLen] + "."
                    pos += segLen

                ip += s[start:]
                result.append(ip)

            return

        for length in range(1, 4):
            if length <= remainingLen:
                segments.append(length)

                if self.isValid(s[start:start + length]):
                    self.backtrack(s, start + length, segments, result)

                segments.pop()

    def restoreIpAddresses(self, s):
        segments = []
        result = []

        self.backtrack(s, 0, segments, result)

        return result

Key Optimizations (Python20)

  1. string_view: Avoids string copying when checking segments and building results
  2. reserve(): Pre-allocates memory for vectors and strings to avoid reallocations
  3. Early Pruning: Checks if remaining digits can form valid segments before recursing
  4. Move Semantics: Uses move() when pushing to result vector
  5. Efficient String Building: Pre-calculates size and uses append() for better performance

Step-by-Step Example: s = "25525511135"

  1. Try first segment “2” (length 1)
    • Valid: 2 (0-255)
    • Recursively try remaining: "5525511135"
  2. Try second segment “5” (length 1)
    • Valid: 5
    • Continue: "525511135"
  3. Continue building…
    • Eventually find: "255.255.11.135" and "255.255.111.35"

Visual Representation

"25525511135"
│
├─ "2" (valid)
│  ├─ "5" (valid)
│  │  ├─ "5" (valid)
│  │  │  └─ "25511135" → try "255", "2551", "25511"...
│  │  └─ "55" (valid)
│  │     └─ ...
│  └─ "55" (valid)
│     └─ ...
└─ "25" (valid)
   └─ ...

Algorithm Breakdown

1. Validation Function

def isValid(self, segment):
    if (segment.length() == 1) return True  // 0-9
    if (segment[0] == '0') return False     # Leading zero
    if (segment.length() == 2) return True  // 10-99
    return segment <= "255"                  // 100-255

2. Backtracking Function

def backtrack(self, s, start, segments, ...):
    # Early pruning
    if remainingLen > remainingCnt * 3  or  remainingLen < remainingCnt:
        return
    # Base case: 3 segments placed
    if len(segments) == 3:
        # Check last segment and build IP
    # Try segments of length 1, 2, 3
    for (len = 1 len <= 3 len += 1) :
    if isValid(s.substr(start, len)):
        backtrack(s, start + len, segments, result)

Complexity

| Aspect | Complexity | |——–|————| | Time | O(1) - At most 3^4 = 81 combinations | | Space | O(1) - At most 19 characters per IP address | | Recursion Depth | O(4) - Maximum 4 segments |

Why This Solution is Optimal

  1. Early Pruning: Eliminates invalid branches immediately
  2. String View: Avoids unnecessary string copies
  3. Memory Pre-allocation: Reduces reallocations
  4. Constant Time: Bounded by maximum 81 combinations
  5. Clean Backtracking: Simple and maintainable

Common Mistakes

  1. All zeros: "0000" → ["0.0.0.0"]
  2. Leading zeros: "010010" → ["0.10.0.10","0.100.1.0"]
  3. Long string: "255255255255" → ["255.255.255.255"]

  4. Short string: "1111" → ["1.1.1.1"]

  5. Not checking leading zeros: "010" is invalid
  6. Not checking range: Numbers must be 0-255
  7. Not pruning early: Should check remaining length
  8. String copying: Use string_view for efficiency
  9. Forgetting base case: Must have exactly 4 segments

Key Takeaways

  • Pattern: Choose / explore / unchoose (this problem)
  • For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.
  • Build solution incrementally; undo (backtrack) when constraints fail.

References