Question: Given a string containing only digits, restore it by returning all possible valid IP address combinations.
So if we're give a string: 25619511135, the output is ["256.195.11.135", "256.195.111.35"]
Let's start with understand IP address,
IP addresses are:
1> divided into 4 parts by "." character.
2> each part is an integer whose range is between 1 to 256.
3> each part if it's a single or double-digit integer aren't preceded by 0 ie,
Integer 1 is represented as 1 and not 01 or 001,
Integer 23 is represented as 23 and not 023.
So based on these observations let's build our algorithm.
For better understanding let's build an iterative version first then jump to backtracking.
1> Iterative
Based on constraints let's code.
function restoreIP(ipAddress){
let res = [];
if(ipAddress.length < 4) return res; //if length of ip adress is < 4 then there's no possibility of generating ip addresses from it.
for(let a=1;a<4;a++){ //length of segment 1
for(let b=1;b<4;b++){ //length of segment 2
for(let c=1;c<4;c++){ //length of segment 3
for(let d=1;d<4;d++){ //length of segment 4
if(a+b+c+d === ipAddress.length){
//the total lengths of segments must be equal to length of input string
let p1 = parseInt(ipAddress.substring(0,a));
//part1 between 0,3 of substring
let p2 = parseInt(ipAddress.substring(a,a+b));
//part2 between 4,6 of substring
let p3 = parseInt(ipAddress.substring(a+b,a+b+c));
//part3 between 7,9 of substring
let p4 = parseInt(ipAddress.substring(a+b+c));
//part4 between 10,12 of substring
if(p1<=255 && p2<=255 && p3<=255 && p4<=255){
let str = p1+'.'+p2+'.'+p3+'.'+p4;
if(str.length == s.length + 3) {
//since for cases like 25525501135, the parseInt() will the zeros in
cases like 255.255.011.35 to 255.255.11.35
// this is invalid since we've to use all the digits in the string
res.push(str);
}
}
}
}
}
}
}
return res;
}
Even though this works, it looks alot like spagetti code (like your cooking skills) and if you write this as your final code during an interview, you won't be able to fluant you're skills.
The above algorithm runs in O(n^4). ( A bit faster than you ? )
Let's convert this into a much readable code with backtracking.
// our shell function
function restoreIP(ipAddress){
let res = [];
backtrack(ipAddress,0,res,[],4,ipAddress.length);
return res;
}
//pass it the string, index, res array to store results
//temp array to store various combinations,segments,
and ipAddress length for verification
function backtrack(s,idx,res,temp,seg,l){
if((seg == 0 && idx < l) || (seg!=0 && idx >= l)) return;
// for cases like
// 1> 255255011135 converts to 255.255.11.135 which doesn't utilize all characters.
// 2> 1111 converts to 111.1.1 which is also invalid
if( seg === 0 && idx === l){
res.push(temp.slice().join('.'))
return;
}
// if all conditions meet then add it to res
// since each segment is of length 3
for(let i=1;i<3;i++){
if(idx+1>l) break;
let chunk = s.substring(idx,idx+i);
// here instead of combining and then verfication
// we validate each segment which helps in reducing total number of computation
// and algorithm runs faster than the time your crush sees you.
if(isValid(chunk)){
temp.push(chunk);
dfs(s,idx+i,res,temp,seg-1,l);
temp.pop();
}
}
}
function isValid(str){
if(str.length > 1 && str[0] == '0') return false;
if(parseInt(str) <= 255) return true;
return false;
}
Unlike the above iterative approach, the backtracking approach looks much cleaner, clever and concise, the skills which your interviewer and crush root for.
Now you know how to flaunt your chad backtracking skills.
I hope you like it!
Github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/restoreIp.js
Top comments (1)
In your Github the for loop conditional is correctly written as this, but not in your example.
for (let i=1;i<=3;i++)
"2> each part is an integer whose range is between 1 to 256"
In your isValid helper function it should be this:
if(parseInt(str) <= 256) return true;
Other than that this was a pretty helpful backtracking solution that helped me understand this problem better.