Generating IP Addresses [Backtracking String problem]

In this article, we will explore a common problem of restoring IP addresses from a given string of digits. For example, given the string "25525511135", the valid IP addresses that can be generated are "255.255.11.135" and "255.255.111.35". With step-by-step guide and helpful tips, you will be able to efficiently and accurately restore all possible IP addresses from the given string without any hassle.

Table of Contents

1. ̥Backtracking
2. Approach
3. Code
4. Analysis

Backtracking

To solve this problem we first need to understand backtracking. Backtracking is a general algorithmic technique for solving problems by exploring all possible solutions in a recursive manner and systematically eliminating those that are not feasible or do not satify the problem's constraints. In this problem, the task is to restore all possible valid IP addresses from a given string of digits, where each IP address must have four segments separated by a dot, and each segment must be between 0 and 255.

Approach

• We start with the input string and try to split it into four segments that can form a valid IP address.
• We try all possible segments lengths(1,2 or 3 digits) and check if each segment is a valid integer between 0 and 255 (leading zeroes are not allowed).
• If we find a valid segment, we add it to our list of segments and if we get four such valid segments then we add it to our list of results.
• If we have not found four valid segments and we still have characters in our input string, we repeat the above two steps for the remaining characters in the string.
• If we have reached the end of the string and still have not found four valid segments, we backtrack to the previous segment and try a different segment length or value.
• We continue this process until we have tried all possible combinations of segments

Code

c++

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<string> res;
    vector<string> segment;
    vector<string> restoreIpAddresses(string s) {
        backtrack(s,0,segment,res);
        return res;
    }

    void backtrack(string s, int idx, vector<string>&segments,  vector<string>&res){
        if(segments.size() == 4 && idx == s.size()){
            res.push_back((segments[0]+"."+segments[1]+"."+segments[2]+"."+segments[3]));
            return;
        }

        if(segments.size() < 4 && idx < s.size()){
        
            for(int i=1; i<=3 && i < s.size(); ++i){
                string seg = s.substr(idx,i);
                if(isvalid(seg)){
                    segment.push_back(seg);
                    backtrack(s,idx+i,segments,res);
                    segment.pop_back();
                }
            }
        }
    }

    bool isvalid(string s){
        if(s.size() > 1 && s[0] == '0')
            return false;
        int val = stoi(s);
        return val >= 0 && val <= 255;
    }
};

int main(){
    Solution s;
    string input =  "29347125";
    vector<string> valid_id = s.restoreIpAddresses(input);
    for(auto id : valid_id){
        cout<<id<<"\n";
    }
}

Java

import java.util.*;

class Solution {
    List<String> res = new ArrayList<>();
    List<String> segment = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        backtrack(s, 0, segment, res);
        return res;
    }

    public void backtrack(String s, int idx, List<String> segments, List<String> res) {
        if (segments.size() == 4 && idx == s.length()) {
            res.add(String.join(".", segments));
            return;
        }

        if (segments.size() < 4 && idx < s.length()) {
        
            for (int i = 1; i <= 3 && idx + i <= s.length(); i++) {
                String seg = s.substring(idx, idx+i);
                if (isvalid(seg)) {
                    segments.add(seg);
                    backtrack(s, idx+i, segments, res);
                    segments.remove(segments.size()-1);
                }
            }
        }
    }

    public boolean isvalid(String s) {
        if (s.length() > 1 && s.charAt(0) == '0') {
            return false;
        }
        int val = Integer.parseInt(s);
        return val >= 0 && val <= 255;
    }
}

class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        String input_str = "29347125";
        List<String> valid_id = s.restoreIpAddresses(input_str);
        for (String id : valid_id) {
            System.out.println(id);
        }
    }
}

Python

class Solution:
    def __init__(self):
        self.res = []
        self.segment = []
        
    def restoreIpAddresses(self, s: str) -> List[str]:
        self.backtrack(s, 0, self.segment, self.res)
        return self.res
        
    def backtrack(self, s: str, idx: int, segments: List[str], res: List[str]) -> None:
        if len(segments) == 4 and idx == len(s):
            res.append('.'.join(segments))
            return
        
        if len(segments) < 4 and idx < len(s):
            # try inserting some numbers to segments
            for i in range(1, 4):
                if idx + i > len(s):
                    break
                seg = s[idx:idx+i]
                if self.isvalid(seg):
                    segments.append(seg)
                    self.backtrack(s, idx+i, segments, res)
                    segments.pop()
                    
    def isvalid(self, s: str) -> bool:
        if len(s) > 1 and s[0] == '0':
            return False
        val = int(s)
        return val >= 0 and val <= 255


if __name__ == '__main__':
    s = Solution()
    input_str = "29347125"
    valid_id = s.restoreIpAddresses(input_str)
    for id in valid_id:
        print(id)

Output:
2.93.47.125
29.3.47.125
29.34.7.125
29.34.71.25

Analysis

The restoreIpAddress function initialized the result vector res and the segment vector segments, and then calls the backtract function with the input string, an initial starting index of 0 and the two vectors which we declared globally.

The backtrack function checks for the base cases described and recursively tries out all possible segment combinations that can form a valid IP address. Tha isvalid function checks if a given segment is a vlid interger between 0 and 255 and also checks for leading zeroes. Overall the backtracking algorithm tries out all possible combinatoins of valid IP address segments that can be formed from the input string, and returns all the valid address that are found.

• Time Complexity:

The time complexity of the code is O(n). (Actually O(3^4 n)), where n is the length of the input string. The reason for this is that for each of the four segments in the IP address, we can have upto 3 digits(0-255). Therefore, the maximum possibility to consider for each segment is 3, and we need to do this for all 4 segments. Additionally, we need to consider every substring which has a maximum lenth of n.