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)
題意：給出一個(gè)字符串，其中都是數(shù)字匠璧，想把它分割成一個(gè)合法的ip地址格式鸣奔，有多少種方法恐锦。
思路：
ip地址的格式是用三個(gè).把一串?dāng)?shù)字分割成四組，每組數(shù)字最大為255，且不能以0開頭。
那么對(duì)于每一位底洗，我們可以選擇把.放在它后面或者放在由它作為數(shù)字首位的兩位數(shù)或者三位數(shù)后面(后面如果有這么多數(shù)字)，比如123可以1.23咕娄、12.3亥揖、123.。這里要注意兩個(gè)條件圣勒，當(dāng)前位如果是0费变，則不能和后面的數(shù)字組合，所以.只有一種放法圣贸，如果組合出三位數(shù)挚歧，三位數(shù)的和不能大于255。
如果我們分割了四組吁峻，并且當(dāng)前分割的位置到了末尾滑负，那么這就是一個(gè)合法的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);
}
}