Restore IP address, dive into backtracking and recursion
Tags: javascript, algorithms
Published: 2020-03-27 12:40:05

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.

```javascript
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.

```javascript

// 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