A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.
For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.
Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s.
You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.
Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]
Explanation: You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.
Restore IP Addresses Solution Overview:-
The restore_ip_addresses function takes a string s as input and returns a list of all possible valid IP addresses that can be formed by inserting dots into s.
The function first checks whether the length of the input string is valid for an IP address (between 4 and 12 digits), and returns an empty list if it is not.
Then, it uses three nested loops to generate all possible combinations of the four integers that make up an IP address.
The first loop iterates from the first digit to the third last digit,
the second loop iterates from the second digit to the second last digit, and the third loop iterates from the third digit to the last digit.
For each combination of integers, the function checks whether each integer is valid according to the rules for IP addresses: each integer must be between 0 and 255
(inclusive), and cannot have leading zeros.
If all four integers are valid, the function adds the IP address to the result list.
The is_valid function is a helper function that checks whether a given string represents a valid integer for an IP address.
It checks whether the string length is between 1 and 3 (inclusive), whether the string starts with a zero and is longer than 1 digit,
and whether the integer value of the string is between 0 and 255 (inclusive).
Note that this function only returns valid IP addresses that can be formed by inserting dots into the input string.
It does not check whether the resulting IP address is actually in use or reachable on a network.
Leetcode 93. Restore IP Addresses Java Solution with Backtracking Approach
There are 3 dots and 4 integers in the valid IP addresses.
So what we can do here is we should try all possible positions to put the dots using backtracking.
Why are we trying to backtrack here, we can try to find another valid IP address if we found an invalid IP address.
Backtracking Algorithm:-
The backtracking algorithmic technique is a general algorithmic technique which we use to search every possible combination to solve a computational problem.
The best thing about this algorithm is that it incrementally builds candidates to the solution and abandons a candidate("backtracks") when it determines that the candidate can not lead to the solution.
Back to our problem: Valid IP address
We will try to find valid IP address logic implementation thru backtracking. Since we will recursively enumerate all the possibilities and whenever we get a new integer because of a dot or 2 integers for the last dot, we check whether the integer is valid,
1. the integer can not have leading 0s other than being 0 itself and
2. it's no larger than 255.
Now think about the possibilities that there are 3 possibilities to add each dot, namely it can be added after 1, 2, or 3 digits from the last dot or the beginning of the string, so there are at most 3^3 = 27 possibilities to add all 3 dots.
Base case to optimise the code
Now think about the input string of the IP address. Is the input string's length longer than 12? if yes then we have to return an empty result since each integer can have 3 digits at most. if any more digits and it would either have leading zeros or be greater than 255.
Let's dig into Approach to Implementation
Create a helper function:-
valid(string s, int startIndex, int length){...}
This helper function will check whether the substring from index start to start+ length is a valid number from 0 to 255.
Now assume that the caller guarantees that the length is in the range of [1,3] and so the logic is to check both the conditions:-
1. if the substring's first character is 0 that is s[startIndex] is '0' then length must be 1.
if the length is 3, then the substring should no larger than 255 lexically. if the length is 1 0r 2 and the first case was not triggered then it will be in the acceptable range.
So, let's design the algorithm to find the valid IP address.
class Solution {
private boolean valid(String s, int start, int length) {
return length == 1 ||
(s.charAt(start) != '0' &&
(length < 3 ||
s.substring(start, start + length).compareTo("255") <= 0));
}
private void helper(String s, int startIndex, List dots, List ans) {
final int remainingLength = s.length() - startIndex;
final int remainingNumberOfIntegers = 4 - dots.size();
if (remainingLength > remainingNumberOfIntegers * 3 ||
remainingLength < remainingNumberOfIntegers) {
return;
}
if (dots.size() == 3) {
if (valid(s, startIndex, remainingLength)) {
StringBuilder sb = new StringBuilder();
int last = 0;
for (Integer dot : dots) {
sb.append(s.substring(last, last + dot));
last += dot;
sb.append('.');
}
sb.append(s.substring(startIndex));
ans.add(sb.toString());
}
return;
}
for (int curPos = 1; curPos <= 3 && curPos <= remainingLength; ++curPos) {
// Append a dot at the current position.
dots.add(curPos);
// Try making all combinations with the remaining string.
if (valid(s, startIndex, curPos)) {
helper(s, startIndex + curPos, dots, ans);
}
// Backtrack, i.e. remove the dot to try placing it at the next position.
dots.remove(dots.size() - 1);
}
}
public List restoreIpAddresses(String s) {
List ans = new ArrayList<>();
helper(s, 0, new ArrayList<>(), ans);
return ans;
}
}
Leetcode 93. Restore IP Addresses Java Solution with Iterative Approach
class Solution {
private boolean isValidSegment(String mySegment, int startIndex, int length) {
boolean length_check = length == 1;
boolean isZeroAtFirstCharInSegment = mySegment.charAt(startIndex) != '0';
boolean isLessThan255 = cond3(mySegment, startIndex, length);
return length_check || (isZeroAtFirstCharInSegment && isLessThan255);
}
boolean cond3(String mySegment, int startIndex, int length){
if(length < 3 || mySegment.substring(startIndex, startIndex + length).compareTo("255") <= 0) return true;
return false;
}
public List<String> restoreIpAddresses(String s) {
List<String> ans = new ArrayList<>();
for (int len1 = Math.max(1, s.length() - 9); len1 <= 3 && len1 <= s.length() - 3; ++len1) {
if (!isValidSegment(s, 0, len1)) {
continue;
}
for (int len2 = Math.max(1, s.length() - len1 - 6); len2 <= 3 && len2 <= s.length() - len1 - 2; ++len2) {
if (!isValidSegment(s, len1, len2)) {
continue;
}
for (int len3 = Math.max(1, s.length() - len1 - len2 - 3); len3 <= 3 && len3 <= s.length() - len1 - len2 - 1; ++len3) {
if (isValidSegment(s, len1 + len2, len3) && isValidSegment(s, len1 + len2 + len3, s.length() - len1 - len2 - len3)) {
ans.add(String.join(".",
s.substring(0, len1),
s.substring(len1, len1 + len2),
s.substring(len1 + len2, len1 + len2 + len3),
s.substring(len1 + len2 + len3)));
}
}
}
}
return ans;
}
}
Leetcode 93. Restore IP Addresses JavaScript Solution
/**
* @param {string} s
* @return {string[]}
*/
var restoreIpAddresses = function(s) {
let res = [];
function backtrack(s, start, temp, dotCount) {
if (start === s.length && dotCount === 4) {
res.push(temp.slice(0, -1));
return;
}
if (start >= s.length || dotCount > 4) return;
for (let i = start; i < start + 3; i++) {
if (i < s.length) {
let sub = s.substring(start, i + 1);
if (isValid(sub)) {
backtrack(s, i + 1, temp + sub + '.', dotCount + 1);
}
}
}
}
backtrack(s, 0, '', 0);
return res;
};
function isValid(s) {
if (s.length > 1 && s[0] === '0') {
return false;
}
if (parseInt(s) > 255) {
return false;
}
return true;
}
