Generate Valid IP Addresses from String
Last Updated : 28 Jan, 2025
Given a String containing only digits, the task is to restore it by returning all possible valid IP address combinations.
A valid IP address must be in the form of A.B.C.D, where A, B, C, and D are numbers from 0-255. The numbers cannot be 0 prefixed unless they are 0.
Examples:
Input: "255678166"
Output: [“25.56.78.166”, “255.6.78.166”, "255.67.8.166", "255.67.81.66"]
Explanation: These are the only valid possible IP addresses.
Input: "25505011535"
Output: []
Explanation: We cannot generate a valid IP address with this string.
Approach - Using Backtracking with pruning
The idea is to use backtracking and prune recursive branches that would lead to invalid IP addresses.
An IP address consists of 4 valid numbers separated by 3 dots. We have to place these 3 dots at positions such that 4 valid numbers are formed.
One key observation is that the next dot can be placed 1, 2, or 3 positions after the last dot, as the numbers formed must not exceed 255. Additionally, before placing a dot, we check if the current number being formed is valid or invalid. If the number is invalid, we will backtrack and explore other available options.
Step by Step implementation
- First place dots in the string to form valid IP segments.
- Check whether the current segment is valid before continuing. If it is invalid prune that recursive branch.
- Stop once 3 dots are placed, ensuring the final segment is valid.
C++ // C++ program to generate all possible valid // ip address using backtracking #include <algorithm> #include <iostream> #include <string> #include <vector> using namespace std; // Function to check whether segment is valid or not. bool isValid(string &s) { int n = s.size(); // Segment of lenght one are always valid if (n == 1) return true; // converting string into integer int val = stoi(s); // Invalid case: If it has preceding zero or // if its value is greater than 255. if (s[0] == '0' || val > 255) return false; return true; } // Recursive helper Function to generate valid IP address void generateIpRec(string &s, int index, string curr, int cnt, vector<string> &res) { string temp = ""; // Base case: Reached end of string and // all 4 segments were not completed if (index >= s.size()) return; if (cnt == 3) { temp = s.substr(index); // Checking 4th(last) segment of ip address if (temp.size() <= 3 && isValid(temp) ) res.push_back(curr+temp); return; } for (int i = index; i < min(index + 3, (int)s.size()); i++) { // creating next segment of ip address. temp = temp + s[i]; // If the created segment is valid. if (isValid(temp)) { // Generate the remaining segments of IP generateIpRec(s, i + 1, curr + temp + '.', cnt + 1, res); } } } // Function to generate valid IP address vector<string> generateIp(string s) { vector<string> res; generateIpRec(s, 0, "", 0, res); return res; } int main() { string s = "255678166"; vector<string> res = generateIp(s); for (string ip : res) cout << ip << endl; } // Java program to generate all possible valid // ip address using backtracking import java.util.ArrayList; class GfG { // Function to check whether segment is valid or not. static boolean isValid(String s) { int n = s.length(); // Segment of length one is always valid if (n == 1) return true; // Converting string into integer int val = Integer.parseInt(s); // Invalid case: If it has a preceding zero or // its value is greater than 255. if (s.charAt(0) == '0' || val > 255) return false; return true; } // Recursive helper function to generate valid IP address static void generateIpRec(String s, int index, String curr, int cnt, ArrayList<String> res) { String temp = ""; // Base case: Reached end of string and // all 4 segments were not completed if (index >= s.length()) return; if (cnt == 3) { temp = s.substring(index); // Checking 4th (last) segment of IP address if (temp.length() <= 3 && isValid(temp)) res.add(curr + temp); return; } for (int i = index; i < Math.min(index + 3, s.length()); i++) { // Creating next segment of IP address temp += s.charAt(i); // If the created segment is valid if (isValid(temp)) { // Generate the remaining segments of IP generateIpRec(s, i + 1, curr + temp + ".", cnt + 1, res); } } } // Function to generate valid IP address static ArrayList<String> generateIp(String s) { ArrayList<String> res = new ArrayList<>(); generateIpRec(s, 0, "", 0, res); return res; } public static void main(String[] args) { String s = "255678166"; ArrayList<String> res = generateIp(s); for (String ip : res) System.out.println(ip); } } # Python program to generate all possible valid # ip address using backtracking # Function to check whether segment is valid or not. def isValid(s): n = len(s) # Segment of length one is always valid if n == 1: return True # Converting string into integer val = int(s) # Invalid case: If it has a preceding zero or # its value is greater than 255 if s[0] == '0' or val > 255: return False return True # Recursive helper function to generate valid IP address def generateIpRec(s, index, curr, cnt, res): temp = "" # Base case: Reached end of string and # all 4 segments were not completed if index >= len(s): return if cnt == 3: temp = s[index:] # Checking 4th (last) segment of IP address if len(temp) <= 3 and isValid(temp): res.append(curr + temp) return for i in range(index, min(index + 3, len(s))): # Creating next segment of IP address temp += s[i] # If the created segment is valid if isValid(temp): # Generate the remaining segments of IP generateIpRec(s, i + 1, curr + temp + ".", cnt + 1, res) # Function to generate valid IP address def generateIp(s): res = [] generateIpRec(s, 0, "", 0, res) return res if __name__ == "__main__": s = "255678166" res = generateIp(s) for ip in res: print(ip)
// C# program to generate all possible valid // ip address using backtracking using System; using System.Collections.Generic; class GfG { // Function to check whether segment is valid or not. static bool isValid(string s) { int n = s.Length; // Segment of length one is always valid if (n == 1) return true; // Converting string into integer int val = int.Parse(s); // Invalid case: If it has a preceding zero or // its value is greater than 255. if (s[0] == '0' || val > 255) return false; return true; } // Recursive helper function to generate valid IP address static void generateIpRec(string s, int index, string curr, int cnt, List<string> res) { string temp = ""; // Base case: Reached end of string and // all 4 segments were not completed if (index >= s.Length) return; if (cnt == 3) { temp = s.Substring(index); // Checking 4th (last) segment of IP address if (temp.Length <= 3 && isValid(temp)) res.Add(curr + temp); return; } for (int i = index; i < Math.Min(index + 3, s.Length); i++) { // Creating next segment of IP address temp += s[i]; // If the created segment is valid if (isValid(temp)) { // Generate the remaining segments of IP generateIpRec(s, i + 1, curr + temp + ".", cnt + 1, res); } } } // Function to generate valid IP address static List<string> generateIp(string s) { List<string> res = new List<string>(); generateIpRec(s, 0, "", 0, res); return res; } static void Main(string[] args) { string s = "255678166"; List<string> res = generateIp(s); foreach (string ip in res) Console.WriteLine(ip); } } // JavaScript program to generate all possible valid // ip address using backtracking // Function to check whether segment is valid or not. function isValid(s) { const n = s.length; // Segment of length one is always valid if (n === 1) return true; // Converting string into integer const val = parseInt(s, 10); // Invalid case: If it has a preceding zero or // its value is greater than 255 if (s[0] === '0' || val > 255) return false; return true; } // Recursive helper function to generate valid IP address function generateIpRec(s, index, curr, cnt, res) { let temp = ""; // Base case: Reached end of string and // all 4 segments were not completed if (index >= s.length) return; if (cnt === 3) { temp = s.substring(index); // Checking 4th (last) segment of IP address if (temp.length <= 3 && isValid(temp)) res.push(curr + temp); return; } for (let i = index; i < Math.min(index + 3, s.length); i++) { // Creating next segment of IP address temp += s[i]; // If the created segment is valid if (isValid(temp)) { // Generate the remaining segments of IP generateIpRec(s, i + 1, curr + temp + ".", cnt + 1, res); } } } // Function to generate valid IP address function generateIp(s) { const res = []; generateIpRec(s, 0, "", 0, res); return res; } // Driver code const s = "255678166"; const res = generateIp(s); res.forEach(ip => console.log(ip)); Output25.56.78.166 255.6.78.166 255.67.8.166 255.67.81.66
Time complexity: O(27*n) = O(n), since total 3 times recursive call is made and number of branches in each recursive call is 3.
Auxiliary Space: O(n), used by temporary strings.
Similar Reads
How to validate an IP address using ReGex Given an IP address, the task is to validate this IP address with the help of Regex (Regular Expression) in C++ as a valid IPv4 address or IPv6 address. If the IP address is not valid then print an invalid IP address. Examples: Input: str = "203.120.223.13" Output: Valid IPv4 Input: str = "000.12.23
5 min read
How to validate MAC address using Regular Expression Given string str, the task is to check whether the given string is a valid MAC address or not by using Regular Expression. A valid MAC address must satisfy the following conditions: It must contain 12 hexadecimal digits.One way to represent them is to form six pairs of the characters separated with
6 min read
Program to validate an IP address Write a program to Validate an IP Address. An IP address is a unique identifier for devices on a network, enabling internet communication. It has two versions: IPv4 and IPv6. We will validate IPv4 and IPv6 addresses separately.Table of ContentIPv4 Addresses ValidationIPv6 Addresses ValidationIPv4 Ad
15+ min read
How to validate an IP address using Regular Expressions in Java Given an IP address, the task is to validate this IP address with the help of Regular Expressions.The IP address is a string in the form "A.B.C.D", where the value of A, B, C, and D may range from 0 to 255. Leading zeros are allowed. The length of A, B, C, or D can't be greater than 3.Examples: Inpu
3 min read
Defanged Version of Internet Protocol Address Given a valid (IPv4) Internet Protocol address S, the task is to find the defanged version of that IP address.Defanged Version of IP Address: is in which every period "." is replaced by "[.]". Examples: Input: S = "1.1.1.1" Output: 1[.]1[.]1[.]1 Input: S = "255.100.50.0" Output: 255[.]100[.]50[.]0 A
5 min read
Python | C++ | Remove leading zeros from an IP address Given an IP address, remove leading zeros from the IP address. Examples: Input : 100.020.003.400 Output : 100.20.3.400 Input :001.200.001.004 Output : 1.200.1.4Recommended PracticeRemove leading zeros from an IP addressTry It! The approach is to split the given string by “.†and then convert it to a
4 min read