Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given “25525511135”,

return [“255.255.11.135”, “255.255.111.35”]. (Order does not matter)

This problem can be solved by recursion, every time get 1, 2 or 3 numbers from the string, if we can get to the final of the string and have got 4 sections this mean a legal IP address.

Some example of illegal results:

For “25525511135”, 2.55.25.111 has 4 sections but doesn’t get to the last number 5.

For “0000”, 0.00.0 gets to the last number, but only has 3 sections.

There are 2 kinds of corner case:

1. The number in the section is bigger than 255, e.g: 25.535.511.135
2. Including usefulness 0 in the section, e.g: for “10001”, 1.00.0.1

Solution:

``````
class Solution {
public:
vector&amp;lt;string&amp;gt; allRes;
void recurseEachSituations(string &amp;amp;res, string &amp;amp;s, int ptr, int index, int num)
{
string resTemp;
if(s.length() - ptr &amp;gt; num - 1)
{
switch(num)
{
case 1:
resTemp = res + s[ptr];
break;
case 2:
if(s[ptr] == '0') return;//corner case 2
resTemp = res + s.substr(ptr, 2);
break;
case 3:
if(stoi(s.substr(ptr,3)) &amp;gt; 255 || s[ptr] == '0') return;//corner case 1 and 2
resTemp = res + s.substr(ptr, 3);
}

if(index &amp;lt; 4) resTemp += ".";
recursiveIpAdd(resTemp, s, ptr + num, index + 1);
resTemp.clear();
}
}

void recursiveIpAdd(string res, string &amp;amp;s, int ptr, int index)
{

if(index &amp;gt; 4)
{
if(ptr &amp;gt;= s.length()) allRes.push_back(res);
return;
}
if(ptr &amp;gt;= s.length()) return;

recurseEachSituations(res, s, ptr, index, 1);//Get 1 number from string
recurseEachSituations(res, s, ptr, index, 2);//Get 2 numbers from string
recurseEachSituations(res, s, ptr, index, 3);//Get 3 numbers from string
}

vector&amp;lt;string&amp;gt; restoreIpAddresses(string s) {
string res;
recursiveIpAdd(res, s, 0, 1);
return allRes;
}
};
4ms
``````