# Question

Formatted question description: https://leetcode.ca/all/93.html

93	Restore IP Addresses

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)



# Algorithm

For the segmentation problem of character strings, add three dots to the input character string and divide the character string into four segments. Each segment must be legal. Seek all possible situations.

Based on so many questions so far, two experiences have been drawn.

• One is that as long as the subsequence or registration problem of a string is encountered, the dynamic programming DP is first considered;
• the other is that as long as all possible situations need to be requested, recursion is first considered.

This question is not a question of seeking a subsequence or registration of a string, but more in line with the second case, so we have to use recursion to solve it.

We use k to represent the number of segments that still need to be divided. If k = 0, it means that three points have been added and four segments have been formed. If the string is just empty at this time, the current divided result will be saved. If k != 0, then for each segment, we use one, two, and three digits to try and judge whether it is legal or not. If it is legal, call recursion to continue dividing the remaining strings, and finally sum All legal combinations

# Code

Java

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

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();

System.out.println(each);
}
}

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

public class Solution {

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;
}
}
}

• // OJ: https://leetcode.com/problems/restore-ip-addresses
// Time: O(1)
// Space: O(1)
class Solution {
private:
vector<string> ans;
void dfs(string &s, int start, int pos, string &ip) {
if (pos == 4) {
if (start == s.size()) ans.push_back(ip);
return;
}
int i = 0;
for (int num = 0; i < 3 && start + i < s.size(); ++i) {
num = num * 10 + s[start + i] - '0';
if (num > 255 || (s[start] == '0' && i)) break;
ip.push_back(s[start + i]);
if (pos < 3) ip.push_back('.');
dfs(s, start + i + 1, pos + 1, ip);
if (pos < 3) ip.pop_back();
}
while (i--) ip.pop_back();
}
public:
string ip;
dfs(s, 0, 0, ip);
return ans;
}
};

• class Solution(object):
"""
:type s: str
:rtype: List[str]
"""
ans = []
n = len(s)

def isValid(num):
if len(num) == 1:
return True
if len(num) > 1 and num != "0" and int(num) <= 255:
return True
return False

for i in range(0, min(3, n - 3)):
a = s[:i + 1]
if not isValid(a):
break
for j in range(i + 1, min(i + 4, n - 2)):
b = s[i + 1:j + 1]
if not isValid(b):
break
for k in range(j + 1, min(j + 4, n - 1)):
c = s[j + 1:k + 1]
d = s[k + 1:]
if not isValid(c):
break
if not isValid(d):
continue
ans.append("{}.{}.{}.{}".format(a, b, c, d))
return ans