Skip to content

Instantly share code, notes, and snippets.

@anil477
Created January 30, 2022 14:46
Show Gist options
  • Save anil477/b3ec2fbd7f0773fbbfe9028578f56d94 to your computer and use it in GitHub Desktop.
Save anil477/b3ec2fbd7f0773fbbfe9028578f56d94 to your computer and use it in GitHub Desktop.
93. Restore IP Addresses
class Solution {
// 93. Restore IP Addresses
// https://leetcode.com/problems/restore-ip-addresses/
public List<String> restoreIpAddresses(String rawIpString) {
List<String> restoredIps = new ArrayList<>();
restoreIps(0, 0, new int[4], rawIpString, restoredIps);
return restoredIps;
}
private void restoreIps(int progressIndex, int currentSegment, int[] ipAddressSegments, String rawIpString, List<String> restoredIps) {
/*
If we have filled 4 segments (0, 1, 2, 3) and we are on the 4th,
we will only record an answer if the string was decomposed fully
*/
if (currentSegment == 4 && progressIndex == rawIpString.length()) {
restoredIps.add(buildIpStringFromSegments(ipAddressSegments));
} else if (currentSegment == 4) {
return;
}
/*
Generate segments to try, a segment can be 1 to 3 digits long.
*/
for (int segLength = 1; segLength <= 3 && progressIndex + segLength <= rawIpString.length(); segLength++) {
// Calculate 1 index past where the segment ends index-wise in the original raw ip string
int onePastSegmentEnd = progressIndex + segLength;
// Extract int value from our snapshot from the raw ip string
String segmentAsString = rawIpString.substring(progressIndex, onePastSegmentEnd);
int segmentValue = Integer.parseInt(segmentAsString);
// Check the "snapshot's" validity - if invalid break iteration
if (segmentValue > 255 || segLength >= 2 && segmentAsString.charAt(0) == '0') {
break;
}
// Add the extracted segment to the working segments
ipAddressSegments[currentSegment] = segmentValue;
// Recurse on the segment choice - when finished & we come back here, the next loop iteration will try another segment
restoreIps(progressIndex + segLength, currentSegment + 1, ipAddressSegments, rawIpString, restoredIps);
}
}
// Helper Function for building IP address from Integer
private String buildIpStringFromSegments(int[] ipAddressSegments) {
return ipAddressSegments[0] + "." + ipAddressSegments[1] + "."+ ipAddressSegments[2] + "." + ipAddressSegments[3];
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment