Valid IP Addresses

Tags

Valid IP Addresses

Category

Strings

Difficulty

Medium

Problem Statement

Given a string of digits, return all possible valid IP addresses that can be formed by inserting three dots into the string. A valid IP address consists of four octets, each being an integer between 0 and 255, and no octet can have leading zeros (except the single digit "0" itself).

Intuition

An IP address has exactly four parts separated by three dots. We need to choose where to place those three dots in the string. Each part must be between 1 and 3 digits long, and the resulting integer must be in [0, 255] with no leading zeros. Since each part has at most 3 characters, the total number of placements is bounded by a small constant, making brute force feasible.

Approach

  1. Use three nested loops (or recursive backtracking) to place three dots at positions i, j, k in the string.
  2. The first dot splits after index i, the second after j, and the third after k, creating four substrings.
  3. For each combination, validate all four substrings:
    • Length between 1 and 3.
    • No leading zeros (length > 1 and starts with '0' is invalid).
    • Integer value between 0 and 255.
  4. If all four parts are valid, join them with dots and add to the result list.
  5. Return all valid IP addresses found.

Pseudocode

function validIPAddresses(string):
    result = []
    for i from 1 to min(3, len(string) - 3):
        for j from i + 1 to min(i + 3, len(string) - 2):
            for k from j + 1 to min(j + 3, len(string) - 1):
                parts = [string[0:i], string[i:j], string[j:k], string[k:]]
                if all parts are valid:
                    result.append(join parts with ".")
    return result

function isValidPart(part):
    if len(part) > 3: return false
    if len(part) > 1 and part[0] == '0': return false
    return int(part) <= 255

Time & Space Complexity

  • Time: O(1) - The three nested loops each run at most 3 iterations, giving at most 27 combinations. Validation is O(1) per combination. The overall work is bounded by a constant.
  • Space: O(1) for the algorithm itself (excluding the output). The output can contain at most 2^32 valid IPs, but for a given string it is much smaller.

Key Insights

  • The problem has a small bounded search space (at most 27 dot placements) making brute force optimal.
  • Leading zero detection is the trickiest validation rule: "0" is valid but "01", "00", "001" are not.
  • Each octet can be 1 to 3 digits, and the string length must be between 4 and 12 for any valid IP to exist.

Edge Cases

  • String length less than 4 or greater than 12: no valid IP addresses exist.
  • String contains only zeros: "0.0.0.0" is the only valid result for "0000".
  • Strings like "010010": must avoid leading zeros, so "0.10.0.10" is valid but "01.0.01.0" is not.
  • Large numbers: "999999999999" produces no valid IPs since all 3-digit parts exceed 255.

Linked mentions