# 93. Restore IP Addresses

## Description

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.

## Solutions

Solution 1: DFS

We define a function $dfs(i)$, which represents the list of IP addresses that can be formed starting from the $i$th position of string $s$.

The execution steps of function $dfs(i)$ are as follows:

If $i$ is greater than or equal to the length of string $s$, it means that we have completed the splicing of four segments of the IP address. At this point, we need to check whether it meets the requirements of the four segments of the IP address. If it does, add the current $IP$ to the answer.

If $i$ is less than the length of string $s$, it means that we still need to splice a segment of the IP address. At this point, we need to determine the value of this segment of the IP address. If the value is greater than $255$, or the current position $i$ is $0$ and the value of several positions after $i$ is greater than $0$, it means that it does not meet the requirements, so we return directly. Otherwise, add it to the IP address list, and continue to search for the next segment of the IP address.

The time complexity is $O(n \times 3^4)$, and the space complexity is $O(n)$. Here, $n$ is the length of string $s$.

• class Solution {
private int n;
private String s;
private List<String> ans = new ArrayList<>();
private List<String> t = new ArrayList<>();

public List<String> restoreIpAddresses(String s) {
n = s.length();
this.s = s;
dfs(0);
return ans;
}

private void dfs(int i) {
if (i >= n && t.size() == 4) {
return;
}
if (i >= n || t.size() >= 4) {
return;
}
int x = 0;
for (int j = i; j < Math.min(i + 3, n); ++j) {
x = x * 10 + s.charAt(j) - '0';
if (x > 255 || (s.charAt(i) == '0' && i != j)) {
break;
}
t.add(s.substring(i, j + 1));
dfs(j + 1);
t.remove(t.size() - 1);
}
}
}

//////

import java.util.ArrayList;
import java.util.List;

public class Restore_IP_Addresses {

public static void main(String[] args) {

// @note:@memorize: test substring boundary
String a = "abc";
// a = a.substring(0, 4); // String index out of range: 4
a = a.substring(0, 3); // ok
System.out.println(a);

Solution s = out.new Solution();

for (String each: (s.restoreIpAddresses("25525511135"))) {
System.out.println(each);
}
}

List<String> list = new ArrayList<>();

public class Solution {
public List<String> restoreIpAddresses(String s) {

if (s.length() < 4 || s.length() > 12 || !s.matches("\\d+")) {
return list;
}

restore(s, "", 0);

return list;
}

// seg: segment, in total 4
private void restore(String s, String result, int seg) {
if (seg == 4) {
if (s.length() == 0) {

// remove last "."
result = result.substring(0, result.length() - 1);

}

return;
}

// for (int i = 0; i < 3; i++) { // @note: out of boundary
for (int i = 0; i < 3 && i < s.length(); i++) {
String thisSeg = s.substring(0, i + 1);

if (isValid(thisSeg)) {
restore(s.substring(i + 1), result + thisSeg + ".", seg + 1);
}
}
}

private boolean isValid(String s) {

// can NOT be: 10.01.1.1
if (s.length() > 1 && s.startsWith("0")) {
return false;
}

int n = Integer.valueOf(s);
if (n > 255) {
return false;
}

return true;
}
}
}


• class Solution {
public:
vector<string> restoreIpAddresses(string s) {
int n = s.size();
vector<string> ans;
vector<string> t;
function<void(int)> dfs = [&](int i) {
if (i >= n && t.size() == 4) {
ans.push_back(t[0] + "." + t[1] + "." + t[2] + "." + t[3]);
return;
}
if (i >= n || t.size() >= 4) {
return;
}
int x = 0;
for (int j = i; j < min(n, i + 3); ++j) {
x = x * 10 + s[j] - '0';
if (x > 255 || (j > i && s[i] == '0')) {
break;
}
t.push_back(s.substr(i, j - i + 1));
dfs(j + 1);
t.pop_back();
}
};
dfs(0);
return ans;
}
};

• class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
def check(i: int, j: int) -> int:
if s[i] == "0" and i != j:
return False
return 0 <= int(s[i : j + 1]) <= 255

def dfs(i: int):
if i >= n and len(t) == 4:
ans.append(".".join(t))
return
if i >= n or len(t) >= 4:
return
for j in range(i, min(i + 3, n)):
if check(i, j):
t.append(s[i : j + 1])
dfs(j + 1)
t.pop()

n = len(s)
ans = []
t = []
dfs(0)
return ans


• func restoreIpAddresses(s string) (ans []string) {
n := len(s)
t := []string{}
var dfs func(int)
dfs = func(i int) {
if i >= n && len(t) == 4 {
ans = append(ans, strings.Join(t, "."))
return
}
if i >= n || len(t) == 4 {
return
}
x := 0
for j := i; j < i+3 && j < n; j++ {
x = x*10 + int(s[j]-'0')
if x > 255 || (j > i && s[i] == '0') {
break
}
t = append(t, s[i:j+1])
dfs(j + 1)
t = t[:len(t)-1]
}
}
dfs(0)
return
}

• function restoreIpAddresses(s: string): string[] {
const n = s.length;
const ans: string[] = [];
const t: string[] = [];
const dfs = (i: number): void => {
if (i >= n && t.length === 4) {
ans.push(t.join('.'));
return;
}
if (i >= n || t.length === 4) {
return;
}
let x = 0;
for (let j = i; j < i + 3 && j < n; ++j) {
x = x * 10 + s[j].charCodeAt(0) - '0'.charCodeAt(0);
if (x > 255 || (j > i && s[i] === '0')) {
break;
}
t.push(x.toString());
dfs(j + 1);
t.pop();
}
};
dfs(0);
return ans;
}


• public class Solution {
private IList<string> ans = new List<string>();
private IList<string> t = new List<string>();
private int n;
private string s;

public IList<string> RestoreIpAddresses(string s) {
n = s.Length;
this.s = s;
dfs(0);
return ans;
}

private void dfs(int i) {
if (i >= n && t.Count == 4) {
return;
}
if (i >= n || t.Count == 4) {
return;
}
int x = 0;
for (int j = i; j < i + 3 && j < n; ++j) {
x = x * 10 + (s[j] - '0');
if (x > 255 || (j > i && s[i] == '0')) {
break;
}