Restore IP Addresses Leetcode Solution

Problem Statement

The Restore IP Addresses LeetCode Solution – “Restore IP Addresses” states that given the string which contains only digits, we need to return all possible valid IP Addresses in any order that can be formed by inserting dots into the string. Note that we’re not allowed to return any digits from the input string.

An IP Address is called valid if:

1. There exist exactly 4 integers between two dots.
2. All the integers are in the range [0,255].

Example:

Input:  s = "25525511135"

Output: ["255.255.11.135","255.255.111.35"]

Explanation:

• We need to place dots over the input string such that each string between two dots is an integer in the range [0,255] and the total number of such strings is exactly 4.
• All possible valid IP Addresses are: [“255.255.11.135″,”255.255.111.35”].

Input:  s = "0000"

Output: ["0.0.0.0"]

Explanation:

• All possible valid IP Addresses are: [“0.0.0.0”].

Approach

Idea:

1. The main idea to solve this problem is to use Recursion.
2. Consider every position of the input string and, there exist two possible cases:
   1. Place a dot over the current position.
   2. Take this character, i.e don’t place the dot over this position.
3. At every step of the recursion, we have the following data:
   1. curr stores the string between two dots.
   2. res stores the possible IP Address.
   3. index stores the current position in the input string.
4. At each index, first, add the character to curr and check whether the integer that we have is in the range [0,255] then, we can move further otherwise return.
5. When we reach the end of the input string, we’ll check whether we have a valid IP Address or not, If yes, insert the IP Address into our answer.

Code

Restore IP Addresses Leetcode C++ Solution:

class Solution {
public:
    vector<string> ans;
    void recurse(string res,string curr,int index,string s){
        if(index==s.length()){
            if(curr.empty() and count(res.begin(),res.end(),'.')==3){
                ans.push_back(res);
            }
            return;
        }
        if(!curr.empty() and stoi(curr)==0){
            return;
        }
        curr.push_back(s[index]);
        if(stoi(curr)>255){
            return;
        }
        recurse(res,curr,index+1,s);
        if(!res.empty()){
            recurse(res+"."+curr,"",index+1,s);
        }
        else{
            recurse(curr,"",index+1,s);
        }
    }
    vector<string> restoreIpAddresses(string s) {
        recurse("","",0,s);
        return ans;
    }
};

Restore IP Addresses Leetcode Java Solution:

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

    private void recurse(String curr, List<String> ans, int index, String temp, int count) {
        if (count > 4){
            return;
        }
        if (count == 4 && index == curr.length()){
            ans.add(temp);
        }
        for (int i=1; i<4; i++) {
            if (index+i > curr.length()){
                break;
            }
            String s = curr.substring(index,index+i);
            if ((s.startsWith("0") && s.length()>1) || (i==3 && Integer.parseInt(s) >= 256)){
                continue;
            }
            recurse(curr, ans, index+i, temp+s+(count==3?"" : "."), count+1);
        }
    }
}

Complexity Analysis for Restore IP Addresses Leetcode Solution

Time Complexity

The time complexity of the above code is O(2^N) since we have two possibilities at every position, either to insert a dot or don’t insert a dot, where N = number length of the input string.

Space Complexity

The space complexity of the above code is O(N). Here, we don’t consider the space used to store the answers as well as space due to the recursion stack.

Reference: https://en.wikipedia.org/wiki/IP_address