Last updated on January 19th, 2025 at 05:59 pm

Here, we see a Restore IP Addresses LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Restore IP Addresses LeetCode Solution

1. Problem Statement

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 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.

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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Backtracking”. Backtracking is a general algorithmic technique that involves exploring all possible solutions by incrementally building candidates and abandoning a candidate as soon as it is determined that it cannot lead to a valid solution.

3. Code Implementation in Different Languages

3.1 Restore IP Addresses C++

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        string ip;
        dfs(s,0,0,ip,result); //paras:string s,start index of s,step(from0-3),intermediate ip,final result
        return result;
    }
    void dfs(string s,int start,int step,string ip,vector<string>& result){
        if(start==s.size()&& step==4){
            ip.erase(ip.end()-1); //remove the last '.' from the last decimal number
            result.push_back(ip);
            return;
        }
        if(s.size()-start>(4-step)*3) return;
        if(s.size()-start<(4-step)) return;
        int num=0;
        for(int i=start;i<start+3;i++){
            num=num*10+(s[i]-'0');
            if(num<=255){
                ip+=s[i];
                dfs(s,i+1,step+1,ip+'.',result);
            }
            if(num==0) break;
        }        
    }
};

3.2 Restore IP Addresses Java

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

private void dfs(String s, int idx, int c, String path, List<String> ret) {
    if (c >= 4) {
        if (idx == s.length()) {
            ret.add(path.substring(0, path.length()-1));
        }
        return;
    }
    for (int i = idx+1; i <= s.length(); i++) {
        if (isValid(s.substring(idx, i))) {
            dfs(s, i, c+1, path + s.substring(idx, i) + '.', ret);
        }
    }
}
private boolean isValid(String s) {
    if (s.startsWith("0") && !s.equals("0")) {
        return false;
    }
    return s.length() < 4 && 0 <= Integer.valueOf(s) && Integer.valueOf(s) < 256;   
    }
}

3.3 Restore IP Addresses JavaScript

var restoreIpAddresses = function(s) {
    const result = []
    
    function permute(arr, str) {
        if(arr.length === 3) {
            if(isValid(str)) result.push([...arr, str]);
            return;
        }
        for(let i = 1; i < 4; i++) {
            let subStr = str.slice(0, i);
            if(!isValid(subStr)) continue;
            permute([...arr, subStr], str.slice(i));
        }
    }
    function isValid(str) {
        if(+str > 255 || !str.length) return false;
        if(str.length >= 2 && str[0] === '0') return false;
        return true;
    }
    permute([], s);
    return result.map(x => x.join('.'))    
};

3.4 Restore IP Addresses Python

class Solution(object):
    def restoreIpAddresses(self, s):
        res = []
        self.dfs(s, 0, "", res)
        return res
    
    def dfs(self, s, index, path, res):
        if index == 4:
            if not s:
                res.append(path[:-1])
            return # backtracking
        for i in xrange(1, 4):
            if i <= len(s):
                if int(s[:i]) <= 255:
                    self.dfs(s[i:], index+1, path+s[:i]+".", res)
                if s[0] == "0":  # here should be careful 
                    break

4. Time and Space Complexity

• Time Complexity: The dominant factor is the number of recursive calls, which is determined by the number of ways to split the string into valid segments. Each segment can have up to 3 digits, and there are 4 segments, leading to (3⁴ = 81) recursive calls in the worst case.
• Space Complexity: The recursion depth is at most 4 (one for each segment), so the auxiliary space used by the call stack is O(4). The space used to store the results is not counted in auxiliary space as it is part of the output.
• Backtracking: The algorithm systematically explores all possible splits and backtracks when a split is invalid, ensuring all valid IPs are found.