## Algorithm

Problem Nmae: 93. Restore IP Addresses

A valid IP address consists of exactly four integers separated by single dots. Each integer is between `0` and `255` (inclusive) and cannot have leading zeros.

• For example, `"0.1.2.201"` and `"192.168.1.1"` are valid IP addresses, but `"0.011.255.245"`, `"192.168.1.312"` and `"192.168@1.1"` are invalid IP addresses.

Given a string `s` containing only digits, return all possible valid IP addresses that can be formed by inserting dots into `s`. You are not allowed to reorder or remove any digits in `s`. You may return the valid IP addresses in any order.

Example 1:

```Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]
```

Example 2:

```Input: s = "0000"
Output: ["0.0.0.0"]
```

Example 3:

```Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
```

Constraints:

• `1 <= s.length <= 20`
• `s` consists of digits only.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
void gen_ip(const char *s, char *buff, int *seglen) {
int i, j, k;
for (i = 0; i  <  4; i ++) {
strncpy(buff, s, seglen[i]);
s += seglen[i];
buff += seglen[i];
*buff = '.';
buff ++;
}
buff --;
*buff = 0;
}
int validate(const char *s, int len) {
int k = 0;

if (len > 1 && *s == '0') return 0;

while (len -- > 0) {
k = k * 10 + *s - '0';
s ++;
}
return k > 255 ? 0 : 1;
}
void bt(const char *s, char ***p, int *psz, int *pn, int total, int usedlen, int *seglen, int d) {
int i, k;
char buff[16];
if (d == 4) {
if (usedlen != total) return;
gen_ip(s, buff, seglen);
if (*psz == *pn) {
*psz *= 2;
*p = realloc(*p, *psz * sizeof(char *));
//assert(*p);
}
(*p)[*pn] = malloc((total + 4) * sizeof(char));
//assert((*p)[*pn]);
strcpy((*p)[*pn], buff);
(*pn) ++;
return;
}
for (i = 1; i  < = 3; i ++) {
if (validate(&s[usedlen], i)) {
seglen[d] = i;
bt(s, p, psz, pn, total, usedlen + i, seglen, d + 1);
}
}
}
char** restoreIpAddresses(char* s, int* returnSize) {
char **p;
int psz, pn;

int seglen[4] = { 0 };

pn = 0;
psz = 10;
p = malloc(psz * sizeof(char *));
//assert(p);

bt(s, &p, &psz, &pn, strlen(s), 0, seglen, 0);

*returnSize = pn;

return p;
}
``````
Copy The Code &

Input

cmd
s = "25525511135"

Output

cmd
["255.255.11.135","255.255.111.35"]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
vector < string> restoreIpAddresses(string s) {
vector<string> temp;
vector<string> ans;

dfs(s, temp, ans);

return ans;
}

void dfs(string s, vector < string> &temp, vector<string> &ans) {
if (temp.size() == 4 && s.length() == 0) {
ans.push_back(temp[0] + "." + temp[1] + "." + temp[2] + "." + temp[3]);
return;
}
else if (temp.size() >= 4) {
return;
}

for(int i = 1; i  < = 3 && i <= s.length(); i++) {
string t = s.substr(0, i);
if (t.length() > 1 && t[0] == '0') break;
if (stoi(t) > 255) break;
temp.push_back(t);
dfs(s.substr(i, s.length() - i), temp, ans);
temp.pop_back();
}
}
};

int main() {
string str = "010010";
Solution s;
vector < string> ret = s.restoreIpAddresses(str);

for (int i = 0; i  <  ret.size(); i++) {
cout << ret[i] << endl;
}
return 0;
}
``````
Copy The Code &

Input

cmd
s = "25525511135"

Output

cmd
["255.255.11.135","255.255.111.35"]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
int n = s.length();
List output = new ArrayList();
backtrack(s, -1, 3, output, segments, n);
return output;
}

private void backtrack(String s, int prevPos, int dots, List < String> output, LinkedList segments, int n) {
int maxPos = Math.min(n - 1, prevPos + 4);
for (int i = prevPos + 1; i  <  maxPos; i++) {
String segment = s.substring(prevPos + 1, i + 1);
if (isValid(segment)) {
if (dots - 1 == 0) {
updateOutput(s, i, n, segments, output);
}
else {
backtrack(s, i, dots - 1, output, segments, n);
}
segments.removeLast();
}
}
}

public void updateOutput(String s, int currPos, int n, LinkedList < String> segments, List output) {
String segment = s.substring(currPos + 1, n);
if (isValid(segment)) {
segments.removeLast();
}
}

public boolean isValid(String segment) {
int m = segment.length();
if (m > 3)
return false;
return (segment.charAt(0) != '0') ? (Integer.parseInt(segment)  < = 255) : (m == 1);
}
}
``````
Copy The Code &

Input

cmd
s = "0000"

Output

cmd
["0.0.0.0"]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
if (s.length < 4 || s.length > 12) return [];
const res = [];
let ans = "";
for (let a = 1; a  < = 3; a++) {
for (let b = 1; b  < = 3; b++) {
for (let c = 1; c  < = 3; c++) {
for (let d = 1; d  < = 3; d++) {
if (a + b + c + d === s.length) {
let A = +s.substr(0, a);
let B = +s.substr(a, b);
let C = +s.substr(a + b, c);
let D = +s.substr(a + b + c, d);
if (A  < = 255 && B <= 255 && C <= 255 && D <= 255) {
if (
((ans = A + "." + B + "." + C + "." + D).length === s.length + 3)
) {
res.push(ans);
}
}
}
}
}
}
}
return res;
};
``````
Copy The Code &

Input

cmd
s = "0000"

Output

cmd
["0.0.0.0"]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
if len(s) > 12: return []
bfs = [(0, '')]
for c in s:
new = []
c = int(c)
for cur, st in bfs:
if cur * 10 + c <= 255 and (st[-1:] != '0' or cur):
new.append((cur * 10 + c, st + str(c)))
if st:
new.append((c, st + '.' + str(c)))
bfs = new
return [st for cur, st in bfs if st.count('.') == 3]
``````
Copy The Code &

Input

cmd
s = "25525511135"

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{

{
public IList < string> RestoreIpAddresses(string s)
{
var results = new List();
return results;
}

private void RestoreIpAddresses(string s, int startIndex, string existedString, int depth, List < string> results)
{
if (startIndex == s.Length && depth == 4)
{
return;
}
if (startIndex == s.Length || depth == 4) { return; }

for (int i = 1; i  <  4; i++)
{
if ((startIndex + i > s.Length) || (i == 2 && s[startIndex] == '0'))
break;
if (i == 3)
{
var num = int.Parse(s.Substring(startIndex, i));
if (num > 255)
break;
}

var newString = string.IsNullOrWhiteSpace(existedString)
? s.Substring(startIndex, i)
: string.Join(".", existedString, s.Substring(startIndex, i));
RestoreIpAddresses(s, startIndex + i, newString, depth + 1, results);
}
}
}
}
``````
Copy The Code &

Input

cmd
s = "25525511135"

Output

cmd
["255.255.11.135","255.255.111.35"]