Program to generate all possible valid IP addresses from given string | Set 2 | C ++ implementation of the approach ; Function to get all the valid ip - addresses ; If index greater than givenString size and we have four block ; Remove the last dot ; Add ip - address to the results ; To add one index to ip - address ; Select one digit and call the same function for other blocks ; Backtrack to generate another possible ip address So we remove two index ( one for the digit and other for the dot ) from the end ; Select two consecutive digits and call the same function for other blocks ; Backtrack to generate another possible ip address So we remove three index from the end ; Select three consecutive digits and call the same function for other blocks ; Backtrack to generate another possible ip address So we remove four index from the end ; Driver code ; Fill result vector with all valid ip - addresses ; Print all the generated ip - addresses
#include <iostream> NEW_LINE #include <vector> NEW_LINE using namespace std ; void GetAllValidIpAddress ( vector < string > & result , string givenString , int index , int count , string ipAddress ) { if ( givenString . size ( ) == index && count == 4 ) { ipAddress . pop_back ( ) ; result . push_back ( ipAddress ) ; return ; } if ( givenString . size ( ) < index + 1 ) return ; ipAddress = ipAddress + givenString . substr ( index , 1 ) + ' . ' ; GetAllValidIpAddress ( result , givenString , index + 1 , count + 1 , ipAddress ) ; ipAddress . erase ( ipAddress . end ( ) - 2 , ipAddress . end ( ) ) ; if ( givenString . size ( ) < index + 2 givenString [ index ] == '0' ) return ; ipAddress = ipAddress + givenString . substr ( index , 2 ) + ' . ' ; GetAllValidIpAddress ( result , givenString , index + 2 , count + 1 , ipAddress ) ; ipAddress . erase ( ipAddress . end ( ) - 3 , ipAddress . end ( ) ) ; if ( givenString . size ( ) < index + 3 || stoi ( givenString . substr ( index , 3 ) ) > 255 ) return ; ipAddress += givenString . substr ( index , 3 ) + ' . ' ; GetAllValidIpAddress ( result , givenString , index + 3 , count + 1 , ipAddress ) ; ipAddress . erase ( ipAddress . end ( ) - 4 , ipAddress . end ( ) ) ; } int main ( ) { string givenString = "25525511135" ; vector < string > result ; GetAllValidIpAddress ( result , givenString , 0 , 0 , " " ) ; for ( int i = 0 ; i < result . size ( ) ; i ++ ) { cout << result [ i ] << " STRNEWLINE " ; } }