題目：

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)

?

題解：

利用循環遞歸解決子問題。對于每個段內數來說，最多3位最少1位，所以在每一層可以循環3次，來嘗試填段。因為IP地址最多4個分段，當層數是3的時候說明已經嘗試填過3個段了，那么把剩余沒填的數段接到結尾即可。

這個過程中要保證的是填的數是合法的，最后拼接的剩余的數也是合法的。

?注意開頭如果是0的話要特殊處理，如果開頭是0，判斷整個串是不是0，不是的話該字符就是非法的。因為001，01都是不對的。

代碼如下：

?1?????public?ArrayList<String>?restoreIpAddresses(String?s)?{??
?2?????????ArrayList<String>?res?=?new?ArrayList<String>();??
?3?????????String?item?=?new?String();
?4?????????if?(s.length()<4||s.length()>12)?
?5?????????return?res;??
?6?????????
?7?????????dfs(s,?0,?item,?res);??
?8?????????return?res;??
?9?????}??
10???????
11?????public?void?dfs(String?s,?int?start,?String?item,?ArrayList<String>?res){??
12?????????if?(start?==?3?&&?isValid(s))?{??
13?????????????res.add(item?+?s);??
14?????????????return;??
15?????????}??
16?????????for(int?i=0;?i<3?&&?i<s.length()-1;?i++){??
17?????????????String?substr?=?s.substring(0,i+1);??
18?????????????if?(isValid(substr))
19?????????????????dfs(s.substring(i+1,?s.length()),?start+1,?item?+?substr?+?'.',?res);??
20?????????}??
21?????}??
22???????
23?????public?boolean?isValid(String?s){??
24?????????if?(s.charAt(0)=='0')
25?????????????return?s.equals("0");??
26?????????????int?num?=?Integer.parseInt(s);
27?????????????
28?????????if(num?<=?255?&&?num?>?0)
29?????????????return?true;
30?????????else
31?????????????return?false;
32?????}?

?Refrence：http://blog.csdn.net/u011095253/article/details/9158449

?

轉載于:https://www.cnblogs.com/springfor/p/3886409.html

總結

以上是生活随笔為你收集整理的Restore IP Addresses leetcode java的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。