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)

``````import java.util.*;
/**
* Created by gzdaijie on 16/6/5
* dfs需注意的地方,假定已确定位数k, 待确定 4 - k
* (1) 剩余的长度应小于等于 (4 - k) * 3
* (2) 每位数值需要小于 255
* (3) 每一位除了0外,不能以0开头
*/
public class Solution {
private List<String> result;

result = new ArrayList<>();
if (s.length() < 4) return result;

String[] tmp = new String[4];
return result;
}

private void ipAddressesDfs(String[] tmp, int index, String s, int k) {
if (index == 4) {
result.add(tmp[0] + "." + tmp[1] + "." + tmp[2] + "." + tmp[3]);
return;
}

int len = s.length();
int sum;
for (int j = 1; j <= 3 && k + j <= len; j++) {
// 剩余的字符串长度不能超过 3 * (3 - index), index从0开始
if (len - k - j > 3 * (3 - index)) continue;

tmp[index] = s.substring(k, k + j);
sum = Integer.parseInt(tmp[index]);
if (sum > 255 ) continue; // 不能大于255
if (j != 1 && tmp[index].charAt(0) == '0') break; // j > 1,不能以0开头

ipAddressesDfs(tmp, index + 1, s, k + j);
}
}
}
``````
updated 2016-06-05 17:10:05