## DEV Community

Akhil

Posted on • Updated on

# Restore IP address, dive into backtracking and recursion

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"]

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
//the total lengths of segments must be equal to length of input string
//part1 between 0,3 of substring
//part2 between 4,6 of substring
//part3 between 7,9 of substring
//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
let res = [];
return res;
}

//pass it the string, index, res array to store results
//temp array to store various combinations,segments,
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') 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.

I hope you like it! 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.