algoadvance

Leetcode 93. Restore IP Addresses

Problem Statement

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

A valid IP address consists of exactly four integers (each integer in the range 0-255) separated by single periods and without leading zeros (except for the number “0” itself).

Clarifying Questions

  1. Input size: What is the length range of the input string?
    • The input string length would be between 0 and 12.
  2. Output order: Does the order of the IP addresses in the output matter?
    • No, the order does not matter.
  3. Edge cases: Do we need to handle invalid inputs such as non-digit characters?
    • According to the problem statement, input will contain only digits.

Strategy

  1. The task is to split the string into four parts such that each part is a valid IP address segment.
  2. A valid segment:
    • Should not be empty and should not be more than 3 characters long.
    • Should not have leading zeros unless it is “0”.
    • Should be in the range 0-255 when converted to an integer.
  3. We can use backtracking to try every possible split of the input string into four segments.

Code

Here is a C++ implementation using backtracking to generate all valid IP addresses from the given string:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    void backtrack(string& s, int start, vector<string>& segments, vector<string>& result) {
        // Base case: if we have 4 segments and we have consumed all characters from the string
        if (segments.size() == 4) {
            if (start == s.size()) {
                result.push_back(segments[0] + "." + segments[1] + "." + segments[2] + "." + segments[3]);
            }
            return;
        }
        
        // Explore segments starting at 'start'
        for (int len = 1; len <= 3; ++len) {
            if (start + len > s.size()) break;  // Prevent overflow
            string segment = s.substr(start, len);
            
            // Check if the segment is valid
            if ((segment[0] == '0' && segment.size() > 1) || (len == 3 && stoi(segment) > 255)) continue;
            
            // Choose
            segments.push_back(segment);
            
            // Explore further with this segment added
            backtrack(s, start + len, segments, result);
            
            // Un-choose (backtrack)
            segments.pop_back();
        }
    }
    
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        vector<string> segments;
        backtrack(s, 0, segments, result);
        return result;
    }
};

int main() {
    Solution sol;
    string input = "25525511135";
    vector<string> result = sol.restoreIpAddresses(input);
    
    for (string ip : result) {
        cout << ip << endl;
    }
    
    return 0;
}

Time Complexity

The time complexity of this approach can be considered O(1) for practical purposes because:

  1. The length of the string can be at most 12, as an IP address consists of at most 4 segments with a maximum of 3 digits each (4 * 3 = 12).
  2. The backtracking function will explore every possible partitioning of the string, which, given the small fixed input size, is effectively constant.

For larger and more generalized inputs, the complexity would largely depend on the depth of recursion and the number of valid segments tried at each step. Nonetheless, due to the constraints of this problem, it remains efficient with a well-bounded number of potential combinations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI