Restore IP Addresses

Problem Statement

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 are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.

A valid IP:

• Has 4 parts (a.b.c.d)
• Each part is between 0 and 255
• No part can have leading zeros, except "0" itself

LeetCode

• https://leetcode.com/problems/restore-ip-addresses/

Constraints

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

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

Different Approaches

1️⃣ Backtracking

🎯 Idea:

• Try to insert dots in all valid positions to split into 4 parts
• At each step:
  • Choose 1 to 3 digits for a segment
  • Check if it's a valid segment
  • Recursively proceed to next segment

Code:

class Solution {
public:
    // Helper function to check if a segment of the IP is valid
    bool valid(string part) {
        // An empty string is not valid
        if (part.empty()) return false;

        // If the segment starts with '0' and is longer than 1 character, it's invalid (e.g., "01", "001")
        if (part.size() > 1 && part[0] == '0') return false;

        // Convert the string to an integer
        int num = stoi(part);

        // Check if the number is within the valid range for an IP segment (0 to 255)
        return num >= 0 && num <= 255;
    }

    // Recursive function to try placing dots and building valid IP addresses
    void solve(vector<string>& result, string& s, int index, int dots, string currStr) {
        // Base case:
        // If we've placed 4 dots and reached the end of the string, it's a valid IP address
        if (dots == 4 && index == s.size()) {
            // Remove the last extra '.' and store the result
            result.push_back(currStr.substr(0, currStr.size() - 1));
            return;
        }

        // If we placed more than 4 dots or went past the string, it's invalid
        if (dots > 4) return;

        // Try to place a dot after 1 to 3 digits
        for (int cut = 1; cut <= 3; cut++) {
            // If the cut goes beyond the string length, stop
            if (index + cut > s.size()) break;

            // Take a part of the string from current index with length = cut
            string part = s.substr(index, cut);

            // Check if this segment is valid
            if (valid(part)) {
                // Recurse with:
                // - index moved forward by `cut` characters
                // - one more dot placed
                // - current segment added to the temporary result string (with a dot)
                solve(result, s, index + cut, dots + 1, currStr + part + ".");
            }
        }
    }

    // Main function to start the process
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;

        // Start recursion from index 0, 0 dots placed, and empty current string
        solve(result, s, 0, 0, "");

        // Return all collected valid IP addresses
        return result;
    }
};

Complexity Analysis:

• Time Complexity:O(1)
  • The max number of valid IPs is bounded.
  • At most 3 choices (1-3 digits) for each of 4 segments = O(3^4) = 0(81)
  • So, it's constant time, although we call it O(1) in practice due to short input limits.
• Space Complexity:O(1)
  • Recursion stack at most depth 4.
  • Output list could hold up to 100 valid IPs in rare case → O(k) for k answers.