Last updated on October 10th, 2024 at 12:02 am

Here, We see Restore IP Addresses LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Restore IP Addresses LeetCode Solution

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

1. Restore IP Addresses Leetcode Solution 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;
        }        
    }
};

2. Restore IP Addresses Leetcode Solution 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. Restore IP Addresses Leetcode Solution 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('.'))    
};

4. Restore IP Addresses Leetcode Solution 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