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:
- 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.
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 thetestClass
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.
7. Download
This was an example of a Java project which generated Ipv4 addresses from a numeric string.
You can download the full source code of this example here: Generate IPv4 Addresses From Numeric String Example