Restore IP Addresses Leetcode Solution

Hello and welcome back to another day of the Leetcode Daily series! We have a very intriguing problem on backtracking ahead of us, so pull up your socks!

Understanding The Problem

Take your time and go through the problem statement.

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.

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.

We must understand why a given IP address might be valid or invalid. Let's go over the given invalid IP addresses in the question and see why exactly they're invalid.

"0.011.255.245": The second segment in this address, "011" has a leading zero. Hence, this address is invalid.
"192.168.1.312": The last segment in this address "312" is greater than "255". Hence, this address is invalid.
"192.168@1.1": No special characters except "." are permitted in an IP address. Hence, this address is invalid.

Once you've understood how to classify a given IP address as valid or invalid, there's not much else to understand in the problem statement. Given a string of numbers, we need to return a list of all possible valid IP addresses.

The requirement that we need to return all possible valid IP addresses, points us toward backtracking. Let's take a look at the intuition required to solve this problem.

Intuition

Let's answer the question of why we need backtracking here before proceeding to the solution to this problem. Whenever you come across a problem that requires you to consider every possible combination of the given input, like the problem of finding valid IP addresses, backtracking comes into the picture.

In order to check all possible IP addresses in a given string, we need to place the dot (".") at different positions and check if the integer formed before the dot is valid (no leading zeros and less than 255) or not.

There are three possibilities where we can place a dot: after one, two or three digits from the last dot or from the beginning of the string. After placing a dot at a location, we check if the integer formed between the current dot and the previous one, or just before the current one in case the dot is the first one, is valid or not. If it is valid, we recursively move forward and continue placing dots in the remaining string. If it isn't valid, we backtrack and try placing the dot at the next spot.

Let's dive into the algorithm we'll be using.

Create the recursive function that we'll use for backtracking. Let's call it helper . The helper function will take the original string s , the processing index start , an array of integers dots which will store the positions of the dots placed so far, and an array of strings ans which will store the valid IP addresses.
Inside the helper function we initialize two variables: remLength = s.length() - start which stores the string length we need to process and remIntegers = 4 - dots.size() which stores the number of integers left to be validated out of 4. When the helper function is first called, remLength will be equal to s.length() and remIntegers will be equal to 4.
We can perform an early return in two cases (can you think why?):
1. If remLength > remIntegers * 3
2. If remLength < remIntegers
If remIntegers == 1 and the last integer (s.substr(start,start+remLength)) is valid, then we've arrived at a valid configuration for an IP address.
1. Then we iterate over the string, placing dots at the relevant positions and construct the IP address' string and store it in the ans array. Use the following method to do so:
  1. Create an empty string temp to store this IP address, and initialize a variable last to 0. last will store the index of the last placed dot.
  2. Iterate over all elements of the array dots . Append s.substr(last,last+dot) and a '.' into the string temp. Increase last by dot and repeat these steps for each dot.
  3. Append s.substr(last,s.length()) to temp. This is the final integer after the last dot.
  4. Add the temp string into ans.
2. Return.
If the remaining integers are more than 1, then the backtracking scene comes into play. We store the number of digits we are including before placing a dot in a variable curr. Iterate over curr from 1 to min(3,remLength) .
1. Place a dot by adding curr into dots.
2. If the integer s.substr(start,start+curr) is valid
  1. Recursively call helper(s,start+curr,dots,ans).
3. Remove the dot that we placed to backtrack.

That's it! Try implementing this algorithm before proceeding to the next section.

Coding Up The Solution

Here's the full solution to this problem. Make sure you attempt to write the code yourself before looking at the solution.

class Solution {
public:
    bool valid(string s,int start, int length){
        return length == 1 or (s[start] != '0' and (length < 3 or s.substr(start,length) <= "255"));
    }
    void helper(string s,int start, vector<int> dots,vector<string>& ans){
        int remLength = s.length() - start;
        int remIntegers = 4 - dots.size();

        if(remLength > remIntegers * 3 or remLength < remIntegers) return;

        if(dots.size() == 3){
            if(valid(s,start,remLength)){
                string temp;
                int last = 0;
                for(int dot : dots){
                    temp.append(s.substr(last,dot));
                    last += dot;
                    temp.append(".");
                }
                temp.append(s.substr(start));
                ans.push_back(temp);
            }
            return;
        }

        for(int curr = 1; curr <= 3 and curr <= remLength; curr++){
            dots.push_back(curr);
            if(valid(s,start,curr)){
                helper(s,start+curr,dots,ans);
            }
            dots.pop_back();
        }
    }
    vector<string> restoreIpAddresses(string s) {
        vector<int> dots;
        vector<string> ans;

        helper(s,0,dots,ans);

        return ans;
    }
};

That's all for today! Hope you enjoyed solving this problem.

Subscribe to my newsletter to never miss a new article! See you tomorrow with another interesting leetcode problem.

Cheers!

Restore IP Addresses Leetcode Solution

Table of contents

Understanding The Problem

Intuition

Coding Up The Solution