# [LeetCode] 93. Restore IP Addresses 复原IP地址

2021年09月15日 阅读数：1

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

Example:java

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

Java:c++

```public class Solution {
List<String> res = new ArrayList<String>();
int len = s.length();
for(int i = 1; i<4 && i<len-2; i++){
for(int j = i+1; j<i+4 && j<len-1; j++){
for(int k = j+1; k<j+4 && k<len; k++){
String s1 = s.substring(0,i), s2 = s.substring(i,j), s3 = s.substring(j,k), s4 = s.substring(k,len);
if(isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)){
}
}
}
}
return res;
}
public boolean isValid(String s){
if(s.length()>3 || s.length()==0 || (s.charAt(0)=='0' && s.length()>1) || Integer.parseInt(s)>255)
return false;
return true;
}
}　　```

Java:git

```public List<String> restoreIpAddresses(String s) {
List<String> solutions = new ArrayList<String>();
restoreIp(s, solutions, 0, "", 0);
return solutions;
}

private void restoreIp(String ip, List<String> solutions, int idx, String restored, int count) {
if (count > 4) return;
if (count == 4 && idx == ip.length()) solutions.add(restored);

for (int i=1; i<4; i++) {
if (idx+i > ip.length()) break;
String s = ip.substring(idx,idx+i);
if ((s.startsWith("0") && s.length()>1) || (i==3 && Integer.parseInt(s) >= 256)) continue;
restoreIp(ip, solutions, idx+i, restored+s+(count==3?"" : "."), count+1);
}
}　　```

Java:app

```public class Solution {
List<String> res = new ArrayList<String>();
for (int a = 1; a < 4; ++a)
for (int b = 1; b < 4; ++b)
for (int c = 1; c < 4; ++c)
for (int d = 1; d < 4; ++d)
if (a + b + c + d == s.length()) {
int A = Integer.parseInt(s.substring(0, a));
int B = Integer.parseInt(s.substring(a, a + b));
int C = Integer.parseInt(s.substring(a + b, a + b + c));
int D = Integer.parseInt(s.substring(a + b + c));
if (A <= 255 && B <= 255 && C <= 255 && D <= 255) {
String t = String.valueOf(A) + "." + String.valueOf(B) + "." + String.valueOf(C) + "." + String.valueOf(D);
if (t.length() == s.length() + 3) res.add(t);
}
}
return res;
}
}
```

Java:post

```public class Solution {
List<String> res = new ArrayList<String>();
helper(s, 0, "", res);
return res;
}
public void helper(String s, int n, String out, List<String> res) {
if (n == 4) {
return;
}
for (int k = 1; k < 4; ++k) {
if (s.length() < k) break;
int val = Integer.parseInt(s.substring(0, k));
if (val > 255 || k != String.valueOf(val).length()) continue;
helper(s.substring(k), n + 1, out + s.substring(0, k) + (n == 3 ? "" : "."), res);
}
}
}
```

Python:url

```class Solution:
# @param s, a string
# @return a list of strings
result = []
return result

def restoreIpAddressesRecur(self, result, s, start, current, dots):
# pruning to improve performance
if (4 - dots) * 3 < len(s) - start or (4 - dots) > len(s) - start:
return

if start == len(s) and dots == 4:
result.append(current[:-1])
else:
for i in xrange(start, start + 3):
if len(s) > i and self.isValid(s[start:i + 1]):
current += s[start:i + 1] + '.'
self.restoreIpAddressesRecur(result, s, i + 1, current, dots + 1)
current = current[:-(i - start + 2)]

def isValid(self, s):
if len(s) == 0 or (s[0] == '0' and s != "0"):
return False
return int(s) < 256
```

C++:rest

```vector<string> restoreIpAddresses(string s) {
vector<string> ret;
string ans;

for (int a=1; a<=3; a++)
for (int b=1; b<=3; b++)
for (int c=1; c<=3; c++)
for (int d=1; d<=3; d++)
if (a+b+c+d == s.length()) {
int A = stoi(s.substr(0, a));
int B = stoi(s.substr(a, b));
int C = stoi(s.substr(a+b, c));
int D = stoi(s.substr(a+b+c, d));
if (A<=255 && B<=255 && C<=255 && D<=255)
if ( (ans=to_string(A)+"."+to_string(B)+"."+to_string(C)+"."+to_string(D)).length() == s.length()+3)
ret.push_back(ans);
}

return ret;
}
```

[LeetCode] 17. Letter Combinations of a Phone Number 电话号码的字母组合