93. Restore IP Addresses

Description

The restoreIpAddresses function generates all possible valid IP addresses from a given string of digits. An IP address consists of four segments separated by periods, where each segment is a number between 0 and 255. The input string does not contain any periods, and the goal is to insert them in such a way that all resulting IP addresses are valid.

Intuition

The problem requires us to split the string into four valid segments, ensuring that each segment is within the range of 0 to 255. Additionally, segments cannot have leading zeros unless they are exactly "0". This constraint guides the formation of potential IP addresses as we explore all valid ways to insert the periods.

Approach

1. Depth-First Search (DFS): - Use a recursive DFS approach to explore all possible ways to split the string into four segments. - At each step, attempt to create a valid segment by iterating through the string and considering substrings up to a length of 3 characters.
2. Base Cases: - If the current segment starts with '0', only "0" itself is a valid segment (to avoid leading zeros). - Stop further exploration if the segment exceeds "255" since it wouldn't be valid. - If we reach the end of the string and have exactly four segments, a valid IP address is formed and added to the result list.
3. Backtracking: - After adding a valid segment to the current path, recursively explore the next segment. - Remove the last added segment (backtrack) and try the next possibility.
4. Joining Segments: - Once four segments are identified and they cover the entire string, join them with periods and add the resulting string to the final list of valid IP addresses.

Complexity

Time Complexity:

The time complexity is (O(3^4)) or (O(81)), as we consider up to 3 characters for each of the 4 segments. However, the actual complexity is lower due to constraints (like leading zeros and the maximum value of 255) which limit the number of valid segments.

Space Complexity:

The space complexity is (O(n)), where (n) is the length of the input string. This accounts for the space used by the recursion stack and the storage of the result list.

Code

C++

class Solution {
public:
    std::vector restoreIpAddresses(std::string s) {
        std::vector res;
        std::vector arr;
        dfs(s, arr, 0, res);
        return res;
    }

private:
    void dfs(const std::string& s, std::vector& arr, int start, std::vector& res) {
        if (start == s.length() && arr.size() == 4) {
            res.push_back(join(arr, '.'));
            return;
        }
        if (start == s.length() || arr.size() == 4) {
            return;
        }
        std::string num = "";
        for (int i = start; i < s.length() && std::stoi(num + s[i]) <= 255; i++) {
            if (s[start] == '0' && i != start) break;
            num += s[i];
            arr.push_back(num);
            dfs(s, arr, i + 1, res);
            arr.pop_back();
        }
    }

    std::string join(const std::vector& vec, char delimiter) {
        std::string result;
        for (int i = 0; i < vec.size(); i++) {
            if (i > 0) {
                result += delimiter;
            }
            result += vec[i];
        }
        return result;
    }
};

Python

class Solution:
    def restoreIpAddresses(self, s: str):
        res = []
        arr = []

        def dfs(s, arr, start):
            if start == len(s) and len(arr) == 4:
                res.append('.'.join(arr))
                return
            if start == len(s) or len(arr) == 4:
                return
            
            num = ''
            for i in range(start, len(s)):
                if int(num + s[i]) > 255:
                    break
                if s[start] == '0' and i != start:
                    break
                num += s[i]
                arr.append(num)
                dfs(s, arr, i + 1)
                arr.pop()

        dfs(s, arr, 0)
        return res

Java

class Solution {
    public List restoreIpAddresses(String s) {
        List res = new ArrayList<>();
        List arr = new ArrayList<>();
        dfs(s, arr, 0, res);
        return res;
    }

    private void dfs(String s, List arr, int start, List res) {
        if (start == s.length() && arr.size() == 4) {
            res.add(String.join(".", arr));
            return;
        }
        if (start == s.length() || arr.size() == 4) {
            return;
        }
        String num = "";
        for (int i = start; i < s.length() && Integer.parseInt(num + s.charAt(i)) <= 255; i++) {
            if (s.charAt(start) == '0' && i != start) break;
            num += s.charAt(i);
            arr.add(num);
            dfs(s, arr, i + 1, res);
            arr.remove(arr.size() - 1);
        }
    }
}

JavaScript

var restoreIpAddresses = function(s) {
    
    const res = [], arr = [];
    function dfs(s, arr, start) {
        if(start === s.length && arr.length === 4) {
            res.push(arr.join('.'));
            return;
        }
        if(start === s.length || arr.length === 4) {
            return;
        }
        let num = '';
        for(let i = start; i < s.length && num + s[i] <= 255; i++) {
            if(s[start] === '0' && i != start) break;
            num += s[i];
            console.log(num);
            arr.push(num);
            dfs(s, arr, i + 1);
            arr.pop();
        }
       
    }
    
    dfs(s, arr, 0);
    return res;
};