給定一串?dāng)?shù)字竞穷，通過(guò)相鄰數(shù)字的左右組合唐责，求出其所有的ip組合，例如"25525511135"的所有組合為：["255.255.11.135", "255.255.111.35"].
該道題可以使用深搜+回溯算法得出符合要求的結(jié)果瘾带。
在每次深搜的每次操作中鼠哥，可以對(duì)數(shù)字進(jìn)行1到3位的截取，如果截取了3次之后再無(wú)可截取時(shí)看政，正好可組合為一個(gè)ip。具體算法如下：
public class JavaTest {
public static void main(String[] args) {
numberToIp("25525511135");
}
private static void numberToIp(String src) {
List<LinkedList<Integer>> result = new ArrayList<>();
numberToIp(src, result, new LinkedList<Integer>(), 0);
// 輸出所有轉(zhuǎn)換的ip結(jié)果
for (LinkedList<Integer> r: result) {
for(int p: r) {
System.out.print(p+" ");
}
System.out.println();
}
}
/**
* @param src 事件源
* @param result 記錄的總結(jié)果
* @param path 一次深搜的結(jié)果
* @param index 當(dāng)前的定位點(diǎn)
*/
private static void numberToIp(String src, List<LinkedList<Integer>> result, LinkedList<Integer> path, int index) {
// 如果path存儲(chǔ)個(gè)數(shù)以達(dá)到4個(gè)于颖，但src仍未截取完嚷兔，則不再需要繼續(xù)截取，
// 因?yàn)閕p只有4位谴垫，該次深搜作廢
if (index < src.length() && path.size() == 4) return;
// 正好截滿(mǎn)4個(gè)，則做該次深搜結(jié)果存儲(chǔ)操作
if (index == src.length() && path.size() == 4) {
result.add((LinkedList<Integer>) path.clone());
return;
}
// 每次可以從index開(kāi)始往后截取i個(gè)位置
for (int i = 1; i <= 3; i++) {
// 越界剪枝
if (index + i <= src.length()) {
int number = Integer.parseInt(src.substring(index, index + i));
// ip邏輯剪枝
if (number > 255) continue;
path.addLast(number);
numberToIp(src, result, path, index + i);
// 該次深搜完畢乳怎，重置前弯，開(kāi)始下一個(gè)深搜
path.removeLast();
}
}
}
}
