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)
一刷
题解：
- 题目给定的restoreIpAddresses方法
这里我们首先确定要用到递归 + 回溯。 并且我们要了解，合理的ipv4地址是由4段组成，而且每一段的值都在 [0 ， 255] 之间
在这个方法里面，我们要做一些基本的边界判断，比如s 是否为null， s的length 是否在 4 和 12之间。
构造好用来递归求解的方法restoreIp，确定好每个要用的参数。
返回结果
- restoreIp方法
这个方法是我们主要进行处理和判断的方法。我们也分为两个部分
判断并返回结果:
当我们用来保存ip地址List ip长度已经等于4的时候
我们判断记录当前position的int pos是否正好等于String s的长度， 假如否，我们返回
否则，这时我们找到一个合理的解。可以建立一个StringBuilder ipSb，重建出这个ip address，将其加入结果集 res中，返回
- 递归求解:
这里我们要从i = pos， 到i < s.length() && i < pos + 3来进行遍历。 因为ip每一部分最多只有3个digit，所以我们有这个pos + 3的constraint
每次先求得当前的ip segment = s.substring(i, pos + 1)
接下来进行判断， 调用isIpValid方法
假如当前ip segment合理， 我们将这段ip segment加入到list ip中
递归调用restoreIp(res, list, s, i + 1)进行下一步求解
进行回溯，去除掉之前加入的这段ip segment
否则我们增加i，继续尝试下一个ip segment， 直到i = pos + 3时跳出循环
- isIpValid方法
这个方法主要用来确定ip segment是否合理：
首先s为null或者""的时候返回false
当s的首字符为'0'的时候，我们要判断是否整个s为"0"。 假如是，我们返回true， 假如否，那么这次切割结果"0x"不合理，我们返回false
求出ip segment的int值，然后返回这个 ipInt是否 >= 0 并且 <= 255
粗略的时间和空间复杂度估计为O(2n)，但因为有很多的剪枝，有substring()，而且n的范围是在4和12之间，所以详细复杂度并不高，但也并不好算。
public class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
if(s == null || s.length()<4 || s.length()>12) return res;
restoreIp(res, new ArrayList<>(), s, 0);
return res;
}
private void restoreIp(List<String> res, List<String> ip, String s, int pos){
if(ip.size() == 4){
if(pos!=s.length()) return;
//changeListToString
String ipString = changeListToString(ip);
res.add(ipString);
}
for(int i=pos; i<s.length() && i<pos+3; i++){//maximum is 3 char
String ipseg = s.substring(pos, i+1);
if(isValid(ipseg)){
ip.add(ipseg);
restoreIp(res, ip, s, i+1);
ip.remove(ip.size()-1);
}
}
}
private String changeListToString(List<String> ip){
StringBuilder sb = new StringBuilder();
for(String str : ip){
sb.append(str).append(".");
}
sb.setLength(sb.length()-1);
return sb.toString();
}
private boolean isValid(String s){
if(s == null || s.length() == 0) return false;
if(s.charAt(0) == '0') return s.equals("0");
int num = Integer.parseInt(s);
return (num>=0 && num<=255);
}
}
二刷
题解：
对于一个str和起始位置，从起始位置分别截取一段长度为1，2，3的字串，然后进入新的一轮dfs.
public class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
if(s == null || s.length()<4 || s.length()>12) return res;
dfs(res, new ArrayList<>(), s, 0);
return res;
}
private void dfs(List<String> res, List<String> ip, String s, int pos){
if(ip.size() == 4){
if(pos!=s.length()) return;
//changeListToString
String ipString = changeListToString(ip);
res.add(ipString);
}
for(int i=pos; i<s.length() && i<pos+3; i++){
String ipseg = s.substring(pos, i+1);
if(isValid(ipseg)){
ip.add(ipseg);
dfs(res, ip, s, i+1);
ip.remove(ip.size()-1);
}
}
}
private String changeListToString(List<String> ip){
StringBuilder sb = new StringBuilder();
sb.append(ip.get(0));
for(int i=1; i<ip.size(); i++){
sb.append(".");
sb.append(ip.get(i));
}
return sb.toString();
}
private boolean isValid(String str){
if(str == null || str.length() == 0) return false;
if(str.charAt(0) == '0') return str.equals("0");
int num = Integer.parseInt(str);
return (num>=0 && num<=255);
}
}
