1.简述：
有效 IP 地址正好由四个整数组成(每个整数在0到255之间，不能含有前导0)，整数之间使用‘.'分隔。
例如："0.1.2.201"和 "192.168.1.一、有效IP 但是“0.011.255.245”、"192.168.1.“192.168@1.1”和“无效IP” 地址。
给出一个只包含数字的字符串s来表示一个 IP 返回所有可能有效的地址 IP 通过在s中插入这些地址.形成。您不能重新排序或删除s中的任何数字。您可以按任何顺序返回答案。
示例 1：输入：s = “2552551135”输出：“255.255.11.135”
示例 2： 输入：s = “0000”输出:[0.000”.0.0"]
示例 3： 输入：s = “101023”输出:[1.0.10.23","1.0.102.3","10.1.10.10.23".3","101.0.2.3"]
2.实现代码： class Solution { static final int SEG_COUNT = 4; List ans = new ArrayList(); int[] segments = new int[SEG_COUNT]; public List restoreIpAddresses(String s) { segments = new int[SEG_COUNT]; dfs(s, 0, 0); return ans; } public void dfs(String s, int segId, int segStart) { // 如果找到了 4 段 IP 字符串已经遍历了地址和地址，那是一个答案 if (segId == SEG_COUNT) { if (segStart == s.length()) { StringBuffer ipAddr = new StringBuffer(); for (int i = 0; i < SEG_COUNT; ++i) { ipAddr.append(segments[i]); if (i != SEG_COUNT - 1) { ipAddr.append('.'); } } ans.add(ipAddr.toString()); } return; } // 假如还没找到 4 段 IP 字符串已经遍历了地址，然后提前回溯 if (segStart == s.length()) { return; } // 如果当前的数字是因为不能有前导零 0，那么这一段 IP 地址只能为 0 if (s.charAt(segStart) == '0') { segments[segId] = 0; dfs(s, segId + 1, segStart + 1); } // 一般情况，枚举每一种可能性并递归 int addr = 0; for (int segEnd = segStart; segEnd < s.length(); ++segEnd) { addr = addr * 10 + (s.charAt(segEnd) - '0'); if (addr > 0 && addr <= 0xFF) { segments[segId] = addr; dfs(s, segId + 1, segEnd + 1); } else { break; } } }}
