Program to generate all possible valid IP addresses from given string

Last Updated : 01 Mar, 2023

Given a string containing only digits, 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: 25525511135
Output: [“255.255.11.135”, “255.255.111.35”]
Explanation:
These are the only valid possible
IP addresses.

Input: "25505011535"
Output: []
Explanation: 
We cannot generate a valid IP
address with this string.

First, we will place 3 dots in the given string and then try out all the possible combinations for the 3 dots.
Corner case for validity:

For string "25011255255"
25.011.255.255 is not valid as 011 is not valid.
25.11.255.255 is not valid either as you are not
allowed to change the string.
250.11.255.255 is valid.

Approach: Split the string with ‘ . ‘ and then check for all corner cases. Before entering the loop, check the size of the string. Generate all the possible combinations using looping through the string. If IP is found to be valid then return the IP address, else simply return the empty list.
Below is the implementation of the above approach:

Implementation:

C++

// C++ program to generate all possible
// valid IP addresses from given string
#include <bits/stdc++.h>
using namespace std;
 
// Function checks whether IP digits
// are valid or not.
int is_valid(string ip)
{
    // Splitting by "."
    vector<string> ips;
    string ex = "";
    for (int i = 0; i < ip.size(); i++) {
        if (ip[i] == '.') {
            ips.push_back(ex);
            ex = "";
        }
        else {
            ex = ex + ip[i];
        }
    }
    ips.push_back(ex);
 
    // Checking for the corner cases
    // cout << ip << endl;
    for (int i = 0; i < ips.size(); i++) {
        // cout << ips[i] <<endl;
        if (ips[i].length() > 3
            || stoi(ips[i]) < 0
            || stoi(ips[i]) > 255)
            return 0;
 
        if (ips[i].length() > 1
            && stoi(ips[i]) == 0)
            return 0;
 
        if (ips[i].length() > 1
            && stoi(ips[i]) != 0
            && ips[i][0] == '0')
            return 0;
    }
    return 1;
}
 
// Function converts string to IP address
void convert(string ip)
{
    int l = ip.length();
 
    // Check for string size
    if (l > 12 || l < 4) {
        cout << "Not Valid IP Address";
    }
 
    string check = ip;
    vector<string> ans;
 
    // Generating different combinations.
    for (int i = 1; i < l - 2; i++) {
        for (int j = i + 1; j < l - 1; j++) {
            for (int k = j + 1; k < l; k++) {
                check = check.substr(0, k) + "."
                        + check.substr(k);
                check
                    = check.substr(0, j) + "."
                      + check.substr(j);
                check
                    = check.substr(0, i) + "."
                      + check.substr(i);
 
                // cout<< check <<endl;
                // Check for the validity of combination
                if (is_valid(check)) {
                    ans.push_back(check);
                    std::cout << check << '\n';
                }
                check = ip;
            }
        }
    }
}
 
// Driver code
int main()
{
    string A = "25525511135";
    string B = "25505011535";
 
    convert(A);
    convert(B);
 
    return 0;
}
 
// This code is contributed by Harshit

Java

// Java Program to generate all possible
// valid IP addresses from given string
import java.util.*;
 
class GFG {
 
    // Function to restore Ip Addresses
    public static ArrayList<String>
    restoreIpAddresses(String A)
    {
        if (A.length() < 3 || A.length() > 12)
            return new ArrayList<>();
        return convert(A);
    }
 
    private static ArrayList<String>
    convert(String s)
    {
        ArrayList<String> l = new ArrayList<>();
        int size = s.length();
 
        String snew = s;
 
        for (int i = 1; i < size - 2;
             i++) {
            for (int j = i + 1;
                 j < size - 1; j++) {
                for (int k = j + 1;
                     k < size; k++) {
                    snew
                        = snew.substring(0, k) + "."
                          + snew.substring(k);
                    snew
                        = snew.substring(0, j) + "."
                          + snew.substring(j);
                    snew
                        = snew.substring(0, i) + "."
                          + snew.substring(i);
 
                    if (isValid(snew)) {
                        l.add(snew);
                    }
                    snew = s;
                }
            }
        }
 
        Collections.sort(l, new Comparator<String>() {
            public int compare(String o1, String o2)
            {
                String a1[] = o1.split("[.]");
                String a2[] = o2.split("[.]");
 
                int result = -1;
                for (int i = 0; i < 4
                                && result != 0;
                     i++) {
                    result = a1[i].compareTo(a2[i]);
                }
                return result;
            }
        });
        return l;
    }
 
    private static boolean isValid(String ip)
    {
        String a[] = ip.split("[.]");
        for (String s : a) {
            int i = Integer.parseInt(s);
            if (s.length() > 3 || i < 0 || i > 255) {
                return false;
            }
            if (s.length() > 1 && i == 0)
                return false;
            if (s.length() > 1 && i != 0
                && s.charAt(0) == '0')
                return false;
        }
 
        return true;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        System.out.println(
            restoreIpAddresses(
                "25525511135")
                .toString());
    }
}
 
// This code is contributed by Nidhi Hooda.

Python3

# Python3 code to check valid possible IP
 
# Function checks whether IP digits
# are valid or not.
def is_valid(ip):
 
    # Splitting by "."
    ip = ip.split(".")
     
    # Checking for the corner cases
    for i in ip:
        if (len(i) > 3 or int(i) < 0 or
                          int(i) > 255):
            return False
        if len(i) > 1 and int(i) == 0:
            return False
        if (len(i) > 1 and int(i) != 0 and
            i[0] == '0'):
            return False
             
    return True
 
# Function converts string to IP address
def convert(s):
     
    sz = len(s)
 
    # Check for string size
    if sz > 12:
        return []
    snew = s
    l = []
 
    # Generating different combinations.
    for i in range(1, sz - 2):
        for j in range(i + 1, sz - 1):
            for k in range(j + 1, sz):
                snew = snew[:k] + "." + snew[k:]
                snew = snew[:j] + "." + snew[j:]
                snew = snew[:i] + "." + snew[i:]
                 
                # Check for the validity of combination
                if is_valid(snew):
                    l.append(snew)
                     
                snew = s
                 
    return l 
 
# Driver code         
A = "25525511135"
B = "25505011535"
 
print(convert(A))
print(convert(B))

C#

using System;
using System.Collections.Generic;
 
// C# program to generate all possible
// valid IP addresses from given string
 
// Driver Code 
class HelloWorld {
     
    // Function checks whether IP digits
    // are valid or not.
    static int is_valid(string ip){
        // Splitting by "."
        List<string> ips = new List<string>();
        string ex = "";
        for (int i = 0; i < ip.Length; i++) {
            if (ip[i] == '.') {
                ips.Add(ex);
                ex = "";
            }
            else {
                ex = ex + ip[i];
            }
        }
        ips.Add(ex);
 
        // Checking for the corner cases
        // cout << ip << endl;
        for (int i = 0; i < ips.Count; i++) {
            // cout << ips[i] <<endl;
            if (ips[i].Length > 3 || Int64.Parse(ips[i]) < 0 || Int64.Parse(ips[i]) > 255)
                return 0;
 
            if (ips[i].Length > 1 && Int64.Parse(ips[i]) == 0)
                return 0;
 
            if (ips[i].Length > 1
                && Int64.Parse(ips[i]) != 0
                && ips[i][0] == '0')
                return 0;
        }
        return 1;
    }
     
    // Function converts string to IP address
    static void convert(string ip){
        int l = ip.Length;
 
        // Check for string size
        if (l > 12 || l < 4) {
            Console.WriteLine("Not Valid IP Address");
        }
 
        string check = ip;
        List<string> ans = new List<string>();
 
        // Generating different combinations.
        for (int i = 1; i < l - 2; i++) {
            for (int j = i + 1; j < l - 1; j++) {
                for (int k = j + 1; k < l; k++) {
                    check = check.Substring(0, k) + "." + check.Substring(k);
                    check = check.Substring(0, j) + "." + check.Substring(j);
                    check = check.Substring(0, i) + "." + check.Substring(i);
 
                    // cout<< check <<endl;
                    // Check for the validity of combination
                    if (is_valid(check) != 0) {
                        ans.Add(check);
                        Console.WriteLine(check);
                    }
                    check = ip;
                }
            }
        }
    }
     
    static void Main() {
        string A = "25525511135";
        string B = "25505011535";
         
        convert(A);
        convert(B);
    }
}
 
// The code is added  by Gautam goel.

Javascript

<script>
 
// JavaScript program to generate all possible
// valid IP addresses from given string
 
// Function checks whether IP digits
// are valid or not.
function is_valid(ip)
{
    // Splitting by "."
    let ips = new Array();
    let ex = "";
    for (let i = 0; i < ip.length; i++) {
        if (ip[i] == '.') {
            ips.push(ex);
            ex = "";
        }
        else {
            ex = ex + ip[i];
        }
    }
    ips.push(ex);
 
    // Checking for the corner cases
  
    for(let i = 0; i < ips.length; i++) {
         
        if (ips[i].length > 3
            || parseInt(ips[i]) < 0
            || parseInt(ips[i]) > 255)
            return 0;
 
        if (ips[i].length > 1
            && parseInt(ips[i]) == 0)
            return 0;
 
        if (ips[i].length > 1
            && parseInt(ips[i]) != 0
            && ips[i][0] == '0')
            return 0;
    }
    return 1;
}
 
// Function converts string to IP address
function convert(ip)
{
    let l = ip.length;
 
    // Check for string size
    if (l > 12 || l < 4) {
        document.write("Not Valid IP Address");
    }
 
    let check = ip;
    let ans = new Array();
 
    // Generating different combinations.
    for (let i = 1; i < l - 2; i++) {
        for (let j = i + 1; j < l - 1; j++) {
            for (let k = j + 1; k < l; k++) {
                check = check.substring(0, k) + "."
                        + check.substring(k,check.length);
                check
                    = check.substring(0, j) + "."
                      + check.substring(j,check.length);
                check
                    = check.substring(0, i) + "."
                      + check.substring(i,check.length);
 
                // Check for the validity of combination
                if (is_valid(check)) {
                    ans.push(check);
                    document.write(check,"</br>");
                }
                check = ip;
            }
        }
    }
}
 
// Driver code
 
    let A = "25525511135";
    let B = "25505011535";
 
    convert(A);
    convert(B);
 
    
// This code is contributed by shinjanpatra
 
 
</script>

Output

255.255.11.135
255.255.111.35

Complexity Analysis:

Time Complexity: O(n^3), where n is the length of the string
Three nested traversal of the string is needed, where n is always less than 12.
Auxiliary Space: O(n).
As extra space is needed.

Another Efficient Approach (Dynamic Programming): There is a dp approach exist for this problem and can be solved in time complexity O(n*4*3)=O(12n)=O(n) and space complexity O(4n).

Approach: We know that there are only 4 parts of the IP. We start iterating from the end of string and goes to the start of string. We create a dp 2D-array of size (4 x N). There can be only 2 values in the dp array i.e. 1(true) or 0(false). dp[0][i] tells if we can create 1 part of IP from the substring starting from i to end of string. Similarly, dp[1][i] tells if we can create 2 parts of IP from the substring starting from i to end of string.

After creating the dp array, we start creating the valid IP addresses. We start from the bottom left corner of the 2D dp array. We only iterate 12 times(worst case) but those also will be the valid IP addresses because we only form valid IP addresses.

Implementation:

C++

#include <bits/stdc++.h>
using namespace std;
 
// C++ Program to generate all possible
// valid IP addresses from given string
vector<string> l;
 
bool isValid(string ip)
{
 
  ip = ip + ".";
  int i = 0;
  int j = 0;
 
  while(i < ip.size()){
    // cout << "hi" << endl;
    string s = "";
    while(ip[j] != '.'){
      s = s + ip[j];
      j++;
    }
    // cout << s << endl;
    int num = stoi(s);
    if(s.size() > 3 || num < 0 || num > 255) return false;
    if(s.size() > 1 && num == 0) return false;
    if(s.size() > 1 && num != 0 && s[0] == '0') return 0;
 
    i = j + 1;
    j = i;
  }
 
  return true;
}
 
void createIpFromDp(vector<vector<int>> dp, int r, int c, string s, string ans)
{
  if (r == 0)
  {
    ans += s.substr(c);
    l.push_back(ans);
    return;
  }
  for (int i = 1;  i <= 3 && c + i < s.size(); i++)
  {
    if (isValid(s.substr(c, i)) && dp[r - 1] == 1)
    {
      createIpFromDp(dp, r - 1, c + i, s, ans + s.substr(c, i) + ".");
    }
  }
}
 
// Function to restore Ip Addresses
vector<string> restoreIpAddresses(string s)
{
  int n = s.size();
 
  if (n < 4 || n > 12)
    return l;
 
  // initialize the dp array
  vector<vector<int>> dp(4, vector<int> (n, -1));
 
  for (int i = 0; i < 4; i++) 
  {
    for (int j = n - 1; j >= 0; j--)
    {
      if (i == 0) 
      {
        // take the substring
        string sub = s.substr(j);
        if (isValid(sub))
        {
          dp[i][j] = 1;
        }
        else if (j < n - 3)
        {
          break;
        }
      }
      else
      {
        if (j <= n - i) 
        {
          for (int k = 1; k <= 3 && j + k <= n; k++)
          {
            string temp = s.substr(j, k);
 
            if (isValid(temp)) 
            {
              if (j + k < n && dp[i - 1][j + k] == 1)
              {
                dp[i][j] = 1;
                break;
              }
            }
          }
        }
      }
    }
  }
 
  if (dp[3][0] == 0)
    return l;
 
 
  // Call function createIpfromDp
  createIpFromDp(dp, 3, 0, s, "");
  return l;
}
 
 
// Driver Code
int main()
{
  // Function call
  vector<string> ans = restoreIpAddresses("25525511135");
 
  cout << "[";
  for(int i = 0; i < ans.size(); i++){
    if(i == ans.size() - 1) cout << ans[i];
    else cout << ans[i] << ", ";
  }
  cout << "]" << endl;
}
 
// This code is contributed by Nidhi Goel.

Java

// Java Program to generate all possible
// valid IP addresses from given string
import java.util.*;
 
class GFG
{
    public static ArrayList<String> list;
     
    // Function to restore Ip Addresses
    public static ArrayList<String>
    restoreIpAddresses(String s)
    {
        int n = s.length();
        list = new ArrayList<>();
        if (n < 4 || n > 12)
            return list;
       
         // initialize the dp array
        int dp[][] = new int[4][n];
        for (int i = 0; i < 4; i++) 
        {
            for (int j = n - 1; j >= 0; j--)
            {
                if (i == 0) 
                {
                    // take the substring
                    String sub = s.substring(j);
                    if (isValid(sub))
                    {
                        dp[i][j] = 1;
                    }
                    else if (j < n - 3)
                    {
                        break;
                    }
                }
                else
                {
                    if (j <= n - i) 
                    {
                        for (int k = 1;
                             k <= 3 && j + k <= n; 
                             k++)
                        {
                            String temp
                                = s.substring(j, j + k);
                            if (isValid(temp)) 
                            {
                                if (j + k < n
                                    && dp[i - 1][j + k]
                                           == 1)
                                {
                                    dp[i][j] = 1;
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }
         
        if (dp[3][0] == 0)
            return list;
       
       
        // Call function createIpfromDp
        createIpFromDp(dp, 3, 0, s, "");
        return list;
    }
   
    public static void createIpFromDp(int dp[][], 
                                      int r,
                                      int c, String s,
                                      String ans)
    {
        if (r == 0)
        {
            ans += s.substring(c);
            list.add(ans);
            return;
        }
        for (int i = 1; 
             i <= 3 && c + i < s.length();
             i++)
        {
            if (isValid(s.substring(c, c + i))
                && dp[r - 1] == 1)
            {
                createIpFromDp(dp, r - 1, c + i, s,
                               ans + 
                               s.substring(c, c + i)
                               + ".");
            }
        }
    }
   
   
    private static boolean isValid(String ip)
    {
        String a[] = ip.split("[.]");
        for (String s : a) 
        {
            int i = Integer.parseInt(s);
            if (s.length() > 3 || i < 0 || i > 255) 
            {
                return false;
            }
            if (s.length() > 1 && i == 0)
                return false;
            if (s.length() > 1 && i != 0
                && s.charAt(0) == '0')
                return false;
        }
 
        return true;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Function call
        System.out.println(
            restoreIpAddresses("25525511135").toString());
    }
}
 
// This code is contributed by Nidhi Hooda.

C#

// Include namespace system
using System;
using System.Collections.Generic;
 
public class GFG {
  static List<String> list;
 
  // Function to restore Ip Addresses
  public static List<String> restoreIpAddresses(String s)
  {
    var n = s.Length;
    list = new List<String>();
    if (n < 4 || n > 12) {
      return list;
    }
     
    // initialize the dp array
    int[, ] dp = new int[4, n];
    for (int i = 0; i < 4; i++) {
      for (int j = n - 1; j >= 0; j--) {
        if (i == 0) 
        {
           
          // take the substring
          var sub = s.Substring(j);
          if (GFG.isValid(sub)) {
            dp[i, j] = 1;
          }
          else if (j < n - 3) {
            break;
          }
        }
        else {
          if (j <= n - i) {
            for (int k = 1;
                 k <= 3 && j + k <= n; k++) {
              var temp
                = s.Substring(j, j + k - j);
              if (GFG.isValid(temp)) {
                if (j + k < n
                    && dp[i - 1, j + k]
                    == 1) {
                  dp[i, j] = 1;
                  break;
                }
              }
            }
          }
        }
      }
    }
    if (dp[3, 0] == 0) {
      return list;
    }
     
    // Call function createIpfromDp
    GFG.createIpFromDp(dp, 3, 0, s, "");
    return list;
  }
  public static void createIpFromDp(int[, ] dp, int r,
                                    int c, String s,
                                    String ans)
  {
    if (r == 0) {
      ans += s.Substring(c);
      list.Add(ans);
      return;
    }
    for (int i = 1; i <= 3 && c + i < s.Length; i++) {
      if (GFG.isValid(s.Substring(c, c + i - c))
          && dp[r - 1, c + i] == 1) {
        GFG.createIpFromDp(
          dp, r - 1, c + i, s,
          ans + s.Substring(c, c + i - c) + ".");
      }
    }
  }
  private static bool isValid(String ip)
  {
    String[] a = ip.Split("[.]");
    foreach(String s in a)
    {
      var i = int.Parse(s);
      if (s.Length > 3 || i < 0 || i > 255) {
        return false;
      }
      if (s.Length > 1 && i == 0) {
        return false;
      }
      if (s.Length > 1 && i != 0 && s[0] == '0') {
        return false;
      }
    }
    return true;
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
 
    // Function call
    Console.WriteLine(string.Join(
      ",", (GFG.restoreIpAddresses("25525511135"))
      .ToArray()));
  }
}
 
// This code is contributed by Aarti_Rathi

Python3

# Python program to generate all possible
# valid IP addresses from given string
 
ans = []
 
def is_valid(ip):
    ip = ip + "."
    i, j = 0, 0
    while i < len(ip):
        s = ""
        while ip[j] != ".":
            s = s + ip[j]
            j += 1
        num = int(s)
        if len(s) > 3 or num < 0 or num > 255:
            return False
        if len(s) > 1 and num == 0:
            return False
        if len(s) > 1 and num != 0 and s[0] == '0':
            return False
        i = j + 1
        j = i
    return True
 
def create_ip_from_dp(dp, r, c, s, res):
    if r == 0:
        res += s
        ans.append(res)
        return
    for i in range(1, 4):
        if c + i < len(s) and is_valid(s) and dp[r - 1] == 1:
            create_ip_from_dp(dp, r - 1, c + i, s, res + s + ".")
 
def restore_ip_addresses(s):
    n = len(s)
    if n < 4 or n > 12:
        return ans
 
    # Initialize the dp array
    dp = [[-1 for j in range(n)] for i in range(4)]
 
    for i in range(4):
        for j in range(n - 1, -1, -1):
            if i == 0:
                sub = s[j:]
                if is_valid(sub):
                    dp[i][j] = 1
                elif j < n - 3:
                    break
            else:
                if j <= n - i:
                    for k in range(1, 4):
                        if j + k <= n:
                            temp = s[j:j + k]
                            if is_valid(temp):
                                if j + k < n and dp[i - 1][j + k] == 1:
                                    dp[i][j] = 1
                                    break
 
    if dp[3][0] == 0:
        return ans
 
    # Call function create_ip_from_dp
    create_ip_from_dp(dp, 3, 0, s, "")
    return ans
 
# Driver Code
if __name__ == "__main__":
    # Function call
    ans = restore_ip_addresses("25525511135")
    print(ans)
 
#This code is contributed by rudra1807raj

Javascript

function isValid(ip) {
  ip = ip + ".";
  let i = 0;
  let j = 0;
  while (i < ip.length) {
    let s = "";
    while (ip[j] !== ".") {
      s = s + ip[j];
      j++;
    }
    let num = parseInt(s);
    if (s.length > 3 || num < 0 || num > 255) return false;
    if (s.length > 1 && num == 0) return false;
    if (s.length > 1 && num !== 0 && s[0] == "0") return false;
    i = j + 1;
    j = i;
  }
  return true;
}
 
function createIpFromDp(dp, r, c, s, ans) {
  if (r == 0) {
    ans += s.substring(c);
    l.push(ans);
    return;
  }
  for (let i = 1; i <= 3 && c + i < s.length; i++) {
    if (isValid(s.substring(c, c + i)) && dp[r - 1] == 1) {
      createIpFromDp(dp, r - 1, c + i, s, ans + s.substring(c, c + i) + ".");
    }
  }
}
 
function restoreIpAddresses(s) {
  let n = s.length;
  if (n < 4 || n > 12) return l;
  let dp = [...Array(4)].map(() => Array(n).fill(-1));
  for (let i = 0; i < 4; i++) {
    for (let j = n - 1; j >= 0; j--) {
      if (i == 0) {
        let sub = s.substring(j);
        if (isValid(sub)) {
          dp[i][j] = 1;
        } else if (j < n - 3) {
          break;
        }
      } else {
        if (j <= n - i) {
          for (let k = 1; k <= 3 && j + k <= n; k++) {
            let temp = s.substring(j, j + k);
            if (isValid(temp)) {
              if (j + k < n && dp[i - 1][j + k] == 1) {
                dp[i][j] = 1;
                break;
              }
            }
          }
        }
      }
    }
  }
  if (dp[3][0] == 0) return l;
  createIpFromDp(dp, 3, 0, s, "");
  return l;
}
 
let l = [];
let ans = restoreIpAddresses("25525511135");
console.log(ans);
//This code is contributed by rudra1807raj

Output

[255.255.11.135, 255.255.111.35]

Complexity Analysis:

Time Complexity: O(n), where n is the length of the string. The dp array creation would take O(4*n*3) = O(12n) = O(n). Valid IP creation from dp array would take O(n).
Auxiliary Space: O(n). As dp array has extra space of size (4 x n). It means O(4n).

Another Approach: (Using Recursion)

Implementation:

C++

#include <iostream>
#include <vector>
using namespace std;
 
void solve(string s, int i, int j, int level, string temp,
           vector<string>& res)
{
    if (i == (j + 1) && level == 5) {
        res.push_back(temp.substr(1));
    }
 
    // Digits of a number ranging 0-255 can lie only between
    // 0-3
    for (int k = i; k < i + 3 && k <= j; k++) {
        string ad = s.substr(i, k - i + 1);
 
        // Return if string starting with '0' or it is
        // greater than 255.
        if ((s[i] == '0'&&ad.size()>1) || stol(ad) > 255)
            return;
 
        // Recursively call for another level.
        solve(s, k + 1, j, level + 1, temp + '.' + ad, res);
    }
}
 
int main()
{
    string s = "25525511135";
    int n = s.length();
 
    vector<string> ans;
 
    solve(s, 0, n - 1, 1, "", ans);
 
    for (string s : ans)
        cout << s << endl;
 
    return 0;
}

Java

/*package whatever //do not write package name here */
 
import java.io.*;
import java.util.*;
 
class GFG {
    static void solve(String s, int i, int j, int level, String temp,
           ArrayList<String>res)
{
    if (i == (j + 1) && level == 5) {
        res.add(temp.substring(1));
    }
 
    // Digits of a number ranging 0-255 can lie only between
    // 0-3
    for (int k = i; k < i + 3 && k <= j; k++) {
        String ad = s.substring(i, k + 1);
 
        // Return if string starting with '0' or it is
        // greater than 255.
        if ((s.charAt(i) == '0'&& ad.length()>1 ) || Integer.valueOf(ad) > 255)
            return;
 
        // Recursively call for another level.
        solve(s, k + 1, j, level + 1, temp + '.' + ad, res);
    }
}
 
 
/* Driver program to test above function*/
public static void main(String args[])
{
    String s = "25525511135";
    int n = s.length();
 
    ArrayList<String> ans = new ArrayList<>();
 
    solve(s, 0, n - 1, 1, "", ans);
 
    for (String s1 : ans)
        System.out.println(s1);
}
}
 
// This code is contributed by shinjanpatra.

Python3

# Python code for the above approach
def solve(s, i, j, level, temp, res):
 
    if (i == (j + 1) and level == 5):
        res.append(temp[1:])
 
    # Digits of a number ranging 0-255 can lie only between
    # 0-3
    k = i
    while(k < i + 3 and k <= j):
         
        ad = s[i: k + 1]
 
        # Return if string starting with '0' or it is
        # greater than 255.
        if ((s[i] == '0' and len(ad) > 1) or int(ad) > 255):
            return
 
        # Recursively call for another level.
        solve(s, k + 1, j, level + 1, temp + '.' + ad, res)    
 
        k += 1
 
# driver code
s = "25525511135"
n = len(s)
ans = []
solve(s, 0, n - 1, 1, "", ans)
for s in ans:
    print(s)
 
# This code is contributed by shinjanpatra

C#

using System;
using System.Collections.Generic;
 
class GFG {
 
  public static void solve(string s, int i, int j, int level, string temp, List<string> res)
  {
    if (i == (j + 1) && level == 5) {
      res.Add(temp.Substring(1));
    }
 
    // Digits of a number ranging 0-255 can lie only between
    // 0-3
    for (int k = i; k < i + 3 && k <= j; k++) {
      string ad = s.Substring(i, k - i + 1);
 
      // Return if string starting with '0' or it is
      // greater than 255.
      if ((s[i] == '0' && ad.Length > 1) || Int64.Parse(ad) > 255)
        return;
 
      // Recursively call for another level.
      solve(s, k + 1, j, level + 1, temp + '.' + ad, res);
    }
  }
 
  static void Main() {
    string s = "25525511135";
    int n = s.Length;
    List<string> ans = new List<string>();
    solve(s, 0, n - 1, 1, "", ans);
    foreach(string x in ans)
    {
      Console.WriteLine(x);
    }
  }
}
 
// The code is contributed by Nidhi goel.

Javascript

<script>
 
// Simple JavaScript program 
 
function solve(s,i,j,level, temp,res)
{
    if (i == (j + 1) && level == 5) {
        res.push(temp.substring(1,));
    }
 
    // Digits of a number ranging 0-255 can lie only between
    // 0-3
    for (let k = i; k < i + 3 && k <= j; k++) {
        let ad = s.substring(i, k + 1);
 
        // Return if string starting with '0' or it is
        // greater than 255.
        if ((s[i] == '0' && ad.length > 1) || parseInt(ad) > 255)
            return;
 
        // Recursively call for another level.
        solve(s, k + 1, j, level + 1, temp + '.' + ad, res);    
    }
}
 
// driver code
 
let s = "25525511135";
let n = s.length;
 
let ans = [];
 
solve(s, 0, n - 1, 1, "", ans);
 
for (let s of ans)
    document.write(s,"</br>");
 
// This code is contributed by shinjanpatra
 
</script>

Output

255.255.11.135
255.255.111.35

A

Abhishek Sharma 44

Improve

Program to generate all possible valid IP addresses from given string | Set 2

Similar Reads

Program to generate all possible valid IP addresses from given string | Set 2

Given a string containing only digits, 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: str = "25525511135" Output: 255.255.11.135 255.255.111.35Input: str = "1111101

Print all valid words from given dictionary that are possible using Characters of given Array

Given a dictionary of strings dict[] and a character array arr[]. Print all valid words of the dictionary that are possible using characters from the given character array.Examples: Input: dict - ["go", "bat", "me", "eat", "goal", boy", "run"] arr[] = ['e', 'o', 'b', 'a', 'm', 'g', 'l']Output: "go", "me", "goal".Explanation: Only all the characters

Find a valid parenthesis sequence of length K from a given valid parenthesis sequence

Given a string S of valid parentheses sequence of length N and an even integer K, the task is to find the valid parentheses sequence of length K which is also a subsequence of the given string. Note: There can be more than one valid sequence, print any of them. Examples: Input: S = "()()()", K = 4Output: ()()Explanation:The string "()()" is a subse

Sort the given IP addresses in ascending order

Given an array arr[] of IP Addresses where each element is a IPv4 Address, the task is to sort the given IP addresses in increasing order.Examples: Input: arr[] = {'126.255.255.255', '169.255.0.0', '169.253.255.255'} Output: '126.255.255.255', '169.253.255.255', '169.255.0.0' Explanation: As the second octet of the third IP Address is less than the

Print all valid words that are possible using Characters of Array

Given a dictionary and a character array, print all valid words that are possible using characters from the array. Examples: Input : Dict - {"go","bat","me","eat","goal", "boy", "run"} arr[] = {'e','o','b', 'a','m','g', 'l'} Output : go, me, goal. Asked In : Microsoft Interview The idea is to use Trie data structure to store dictionary, then search

Generate all possible combinations of at most X characters from a given array

Given an array arr[] consisting of N characters, the task is to generate all possible combinations of at most X elements ( 1 ? X ? N). Examples: Input: N = 3, X = 2, arr[] = {'a', 'b', 'a'}Output: a b c bc ca ab cb ac baExplanation: All possible combinations using 1 character is 3 {'a', 'b', 'c'}. All possible combinations using 2 characters are {"

Generate all possible strings formed by replacing letters with given respective symbols

Given a string S consisting of N characters and an array M[] of pairs of characters such that any character M[i][0] can be replaced with the character M[i][1] in the string S, the task is to generate all the possible strings formed by replacing some characters of the string with their respective symbols in the array M[]. Examples: Input: S = "aBc”,

Generate all possible sorted arrays from alternate elements of two given sorted arrays

Given two sorted arrays A and B, generate all possible arrays such that the first element is taken from A then from B then from A, and so on in increasing order till the arrays are exhausted. The generated arrays should end with an element from B. Example: A = {10, 15, 25} B = {1, 5, 20, 30} The resulting arrays are: 10 20 10 20 25 30 10 30 15 20 1

Generate a string whose all K-size substrings can be concatenated to form the given string

Given a string str of size N and an integer K, the task is to generate a string whose substrings of size K can be concatenated to form the given string. Examples: Input: str = "abbaaa" K = 2 Output: abaa Explanation: All substring of size 2 of parent string "abaa" are "ab", "ba" and "aa". After concatenating all these substrings, the given string "

Extracting email addresses using regular expressions in Python

Let suppose a situation in which you have to read some specific data like phone numbers, email addresses, dates, a collection of words etc. How can you do this in a very efficient manner?The Best way to do this by Regular Expression. Let take an example in which we have to find out only email from the given input by Regular Expression. Examples: In

Article Tags :

Practice Tags :