Core Java

Generate IPv4 Addresses From Numeric String Example

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:

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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

01
02
03
04
05
06
07
08
09
10
11
12
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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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

01
02
03
04
05
06
07
08
09
10
11
12
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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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

01
02
03
04
05
06
07
08
09
10
11
12
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.

generate ipv4 from a numeric string
Figure 2. Test 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
Do you want to know how to develop your skillset to become a Java Rockstar?
Subscribe to our newsletter to start Rocking right now!
To get you started we give you our best selling eBooks for FREE!
1. JPA Mini Book
2. JVM Troubleshooting Guide
3. JUnit Tutorial for Unit Testing
4. Java Annotations Tutorial
5. Java Interview Questions
6. Spring Interview Questions
7. Android UI Design
and many more ....
I agree to the Terms and Privacy Policy

Mary Zheng

Mary graduated from the Mechanical Engineering department at ShangHai JiaoTong University. She also holds a Master degree in Computer Science from Webster University. During her studies she has been involved with a large number of projects ranging from programming and software engineering. She worked as a lead Software Engineer where she led and worked with others to design, implement, and monitor the software solution.
Subscribe
Notify of
guest


This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Back to top button