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)
题意：给出一个字符串，其中都是数字，想把它分割成一个合法的ip地址格式，有多少种方法。
思路：
ip地址的格式是用三个.把一串数字分割成四组，每组数字最大为255，且不能以0开头。
那么对于每一位，我们可以选择把.放在它后面或者放在由它作为数字首位的两位数或者三位数后面(后面如果有这么多数字)，比如123可以1.23、12.3、123.。这里要注意两个条件，当前位如果是0，则不能和后面的数字组合，所以.只有一种放法，如果组合出三位数，三位数的和不能大于255。
如果我们分割了四组，并且当前分割的位置到了末尾，那么这就是一个合法的ip。
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);
}
}