Generate IPv4 Addresses From Numeric String Example

Mary ZhengFebruary 14th, 2025Last Updated: February 13th, 2025

0 118 6 minutes read

1. Introduction

Internet Protocol version 4 (IPv4) is a 32-bit number that consists of four 8-bit sections (octets). Each octet is written as a decimal number (ranging from 0 to 255), and the four octets are separated by periods (dots). Applications may store the numeric IPv4 value and generate the dotted formatted string. In this example, I will create a simple Java program to generate IPv4 from a numeric string with three approaches:

Iterative Approach
Backtracking Algorithm Approach
Dynamic Programming Approach

2. Setup

In this step, I will create a simple Java program in Eclipse IDE. The BaseCass has three children that implement the parseIpAddress methods with different approaches.

generate ipv4 from a numeric string — Figure 1 Super Base Class

2.1 Base Class

In this step, I will create a BaseClass.java that includes several constants and three methods to validate and parse IPv4 Addresses from an IPv4 numeric string.

parseIpAddress – returns a list of valid IPv4 addresses from the numeric string. This is an abstract method and will be implemented in the child class with a different approach.
isValidOctet – returns true if the numeric value is between 0 and 255 (inclusive).
isValidIpv4NumericString – returns true if the number value length is between 1 and 12 ( inclusive).

BaseClass.java

package org.zheng.demo;
 
import java.util.List;
 
public abstract class BaseClass {
 
    protected static final int IP_V4_SEGMENT_COUNT = 4;
    protected static final String IPV4_SEPARATOR = ".";
    private static final int MAX_IP_SEGMENT_VALUE = 255;
    private static final int MIN_IP_SEGMENT_VALUE = 0;
    private static final String ZERO = "0";
 
    public BaseClass() {
        super();
    }
 
    protected boolean isValidOctet(final String segment) {
        // Leading zeros are not allowed unless it's just "0"
        if (segment.length() > 1 && segment.startsWith(ZERO)) {
            return false;
        }
 
        int num = Integer.parseInt(segment);
        return num >= MIN_IP_SEGMENT_VALUE && num <= MAX_IP_SEGMENT_VALUE;
    }
 
    protected boolean isValidIpv4NumericString(final String rawIpNumber) {
        return rawIpNumber.length() >= 1 && rawIpNumber.length() <= 12;
    }
 
    public abstract List<String> parseIpAddress(final String rawString);
 
}

Line 31: defines the abstract method: parseIpAddress.

2.2 Base Test

In this step, I will create a BaseTest.java that verifies all methods working as expected.

BaseTest.java

package org.zheng.demo;
 
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertTrue;
 
import java.util.List;
 
import org.junit.jupiter.api.Test;
 
public abstract class BaseTest {
 
    protected BaseClass testClass;
 
    @Test
    void test_isValid_for_bad_larger() {
        assertFalse(testClass.isValidOctet("256"));
    }
 
    @Test
    void test_isValid_for_bad_startzero() {
        assertFalse(testClass.isValidOctet("01"));
    }
 
    @Test
    void test_isValid_for_bad_startzeroo() {
        assertFalse(testClass.isValidOctet("001"));
    }
 
    @Test
    void test_isValid_for_good() {
        for (int i = 0; i <= 255; i++) {
            assertTrue(testClass.isValidOctet("0"));
        }
    }
 
    @Test
    void testParseIpAddress() {
        List possibleIps = testClass.parseIpAddress("196255111253");
        assertEquals(1, possibleIps.size());
        assertEquals("196.255.111.253", possibleIps.get(0));
    }
 
    @Test
    void testParseIpAddress_bad_0() {
        List possibleIps = testClass.parseIpAddress("12");
        assertEquals(0, possibleIps.size());
    }
 
    @Test
    void testParseIpAddress_bad_1() {
        List possibleIps = testClass.parseIpAddress("25825511135");
        assertEquals(0, possibleIps.size());
    }
 
    @Test
    void testParseIpAddress_bad_2() {
        List possibleIps = testClass.parseIpAddress("25505011535");
        assertEquals(0, possibleIps.size());
    }
 
    @Test
    void testParseIpAddress_bad_3() {
        List possibleIps = testClass.parseIpAddress("25505011535666");
        assertEquals(0, possibleIps.size());
    }
 
    @Test
    void testParseIpAddress2() {
        List possibleIps = testClass.parseIpAddress("25525511135");
        assertEquals(2, possibleIps.size());
        assertTrue(possibleIps.contains("255.255.11.135"));
        assertTrue(possibleIps.contains("255.255.111.35"));
    }
 
}

Line 39-41: verifies the “196255111253” can be parsed out as “196.255.111.253“.
Line 70-73: verifies the “25525511135” can be parsed out as “255.255.11.135” and “255.255.111.35“.

3. Iterative Approach

In this step, I will create an IterativeImpl.java that extends from BaseClass and generates all possible IPv4 addresses from a given numeric string via an iterative approach.

Iterate Over All Possible Splits:
- Since the IPv4 address consists of four parts. Split the string into four parts using nested loops. Each loop controls the number of characters for the segment.
Form the IPv4 if finds:
- For each combination of segments, check if each part is a valid IPv4 segment. If all segments are valid, join them with dots and add to the result.

IterativeImpl.java

package org.zheng.demo;
 
import java.util.ArrayList;
import java.util.List;
 
public class IterativeImpl extends BaseClass {
 
    @Override
    public List<String> parseIpAddress(String rawString) {
        List<String> result = new ArrayList<>();
        if (isValidIpv4NumericString(rawString)) {
 
            int rawStringLength = rawString.length();
 
            // Try all 4 possible splits for each segment of the IP address
            for (int i = 1; i < Math.min(IP_V4_SEGMENT_COUNT, rawStringLength); i++) {
                for (int j = i + 1; j < Math.min(i + IP_V4_SEGMENT_COUNT, rawStringLength); j++) {
                    for (int k = j + 1; k < Math.min(k + IP_V4_SEGMENT_COUNT, rawStringLength); k++) {
                        // Split the string into 4 parts
                        String part1 = rawString.substring(0, i);
                        String part2 = rawString.substring(i, j);
                        String part3 = rawString.substring(j, k);
                        String part4 = rawString.substring(k);
 
                        // Check if each part is a valid IP segment
                        if (isValidOctet(part1) && isValidOctet(part2) && isValidOctet(part3) && isValidOctet(part4)) {
                            // If all parts are valid, join them with a dot and add to the result
                            result.add(
                                    part1 + IPV4_SEPARATOR + part2 + IPV4_SEPARATOR + part3 + IPV4_SEPARATOR + part4);
                        }
                    }
                }
            }
        }
        return result;
    }
}

Line 20-23: parse the IPv4 segments.
Line 26-28: add to the returning result if the IPv4 segments are valid.

The time complexity of the approach is O(n^3) where n is the length of the string. This is due to the three nested loops which check all possible ways to split the string into four segments. The string slicing and validation are linear in the length of each part, but since we are only considering four parts, this complexity is manageable for typical input sizes.

3.1 IterativeImplTest

In this step, I will create an IterativeImplTest.java.

IterativeImplTest.java

package org.zheng.demo;
 
import org.junit.jupiter.api.BeforeEach;
 
class IterativeImplTest extends BaseTest {
 
    @BeforeEach
    public void setup() {
        testClass = new IterativeImpl();
    }
 
}

Line 9: assigns a new IterativeImpl object to the testClass variable.

4. Backtracking Algorithm Approach

In this step, I will create a BacktrackImpl.java that extends from BaseClass. The Backtracking Algorithm approach works by recursively trying out different paths and if one doesn’t work, then backtrack and try another until they find the right one.

Use recursion to try splitting the string into segments.
Ensure each segment is valid.
When four segments are formed, check if we have consumed the entire string, and if so, record the valid IPv4 address.

BacktrackImpl.java

package org.zheng.demo;
 
import java.util.ArrayList;
import java.util.List;
 
public class BacktrackImpl extends BaseClass {
 
    private void backTrack(final String rawNumString, final int index, final String current, final int cnt,
            final List<String> results) {
 
        String temp = "";
        if (index >= rawNumString.length()) {
            return;
        }
 
        if (cnt == IP_V4_SEGMENT_COUNT - 1) {
            temp = rawNumString.substring(index);
            if (temp.length() <= IP_V4_SEGMENT_COUNT - 1 && isValidOctet(temp)) {
                results.add(current + temp);
            }
            return;
        }
 
        for (int i = index; i < Math.min(index + IP_V4_SEGMENT_COUNT - 1, rawNumString.length()); i++) {
            temp += rawNumString.charAt(i);
            if (isValidOctet(temp)) {
                backTrack(rawNumString, i + 1, current + temp + IPV4_SEPARATOR, cnt + 1, results);
            }
        }
 
    }
 
    public List<String> parseIpAddress(final String rawString) {
        List<String> parsedOutIps = new ArrayList<>();
        if (isValidIpv4NumericString(rawString)) {
            backTrack(rawString, 0, "", 0, parsedOutIps);
        }
        return parsedOutIps;
    }
}

Line 8: defines the recursive function backTrack to parse the valid IPv4 segments.
Line 27: calls the backTrack method recursively with a different index.
Line 36: calls the backTrack method from the beginning of the index(0).

4.1 BacktrackImplTest

In this step, I will create a BacktrackImplTest.java and assign the testClass variable to a new BacktrackImpl object.

BacktrackImplTest.java

package org.zheng.demo;
 
import org.junit.jupiter.api.BeforeEach;
 
class BacktrackImplTest extends BaseTest {
 
    @BeforeEach
    public void setup() {
        testClass = new BacktrackImpl();
    }
 
}

5. Dynamic Programming Approach

In this step, I will create a DynamicImpl.java that uses backtracking to explore all possible ways to split the string into four valid segments. Dynamic programming is used to store intermediate results and avoid recalculating the same subproblems.

DynamicImpl.java

package org.zheng.demo;
 
import java.util.ArrayList;
import java.util.List;
 
public class DynamicImpl extends BaseClass {
 
    private void generate(final String rawNumString, final int position, final List<String> current,
            final List<String> results) {
 
        if (current.size() == IP_V4_SEGMENT_COUNT) {
            if (position == rawNumString.length()) {
                results.add(String.join(IPV4_SEPARATOR, current));
            }
            return;
        }
 
        for (int j = 1; j <= IP_V4_SEGMENT_COUNT - 1; j++) {
            int tempP = position + j;
            if (tempP > rawNumString.length()) {
                break;
            }
 
            String segment = rawNumString.substring(position, tempP);
            if (isValidOctet(segment)) {
                current.add(segment);
                generate(rawNumString, position + j, current, results);
                current.remove(current.size() - 1);
            }
        }
    }
 
    public List<String> parseIpAddress(final String rawString) {
        List<String> parsedOutIps = new ArrayList<>();
        if (isValidIpv4NumericString(rawString)) {
            generate(rawString, 0, new ArrayList<>(), parsedOutIps);
        }
        return parsedOutIps;
    }
}

Line 26: the intermediate result is added.
Line 28: the intermediate result is removed as not the right segment.

The time complexity is O(3^4) because it considers 3 possible lengths (1, 2, or 3) for each of the four segments. This gives us 3^4 combinations of segments to check. The actual work in checking validity is linear in terms of the length of the string, so the overall complexity is manageable.

5.1 DynamicImplTest

In this step, I will create a DynamicImplTest.java to verify the logic works as expected.

DynamicImplTest.java

package org.zheng.demo;
 
import org.junit.jupiter.api.BeforeEach;
 
class DynamicImplTest extends BaseTest {
 
    @BeforeEach
    public void setup() {
        testClass = new DynamicImpl();
    }
 
}

6. Conclusion

In this example, I created several classes to generate the IPv4 addresses from a numeric string from iterative, backtracking, and dynamic programming approaches. I also verified with Junit5 test classes. As Figure 2 shows, the Dynamic Programming approach performs best as it saves the intermediate results.

7. Download

This was an example of a Java project which generated Ipv4 addresses from a numeric string.

Download
You can download the full source code of this example here: Generate IPv4 Addresses From Numeric String Example

Generate IPv4 Addresses From Numeric String Example

1. Introduction

2. Setup

2.1 Base Class

2.2 Base Test

3. Iterative Approach

3.1 IterativeImplTest

4. Backtracking Algorithm Approach

4.1 BacktrackImplTest

5. Dynamic Programming Approach

5.1 DynamicImplTest

6. Conclusion

7. Download

Thank you!

Mary Zheng

Thank you!

1. Introduction

2. Setup

2.1 Base Class

2.2 Base Test

3. Iterative Approach

3.1 IterativeImplTest

4. Backtracking Algorithm Approach

4.1 BacktrackImplTest

5. Dynamic Programming Approach

5.1 DynamicImplTest

6. Conclusion

7. Download

Thank you!

Related Articles

Thank you!