还原 IP 地址
题目形容：给定一个只蕴含数字的字符串，用以示意一个 IP 地址，返回所有可能从 s 取得的 无效 IP 地址 。你能够按任何程序返回答案。
无效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 无效 IP 地址，然而 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 有效 IP 地址。
示例阐明请见LeetCode官网。
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
解法一：回溯算法
IP地址分为4段，记录每一段的IP地址的值，而后从第一段开始解决，递归进行判断前面的IP地址是否符合条件。
import java.util.ArrayList;import java.util.List;public class LeetCode_093 { // IP地址一共有4段 private static final int SEG_COUNT = 4; // IP地址4段的值别离是多少 private static int[] segments; // 后果集 private static List<String> result = new ArrayList<>(); public static List<String> restoreIpAddresses(String s) { segments = new int[SEG_COUNT]; dfs(s, 0, 0); return result; } /** * 回溯算法 * * @param s 原始字符串 * @param segId 以后是第几段IP地址 * @param segStart 以后第segId段IP地址的起始地位 */ private static void dfs(String s, int segId, int segStart) { // 如果找到了4段IP地址并且遍历完了字符串，则阐明以后后果是一种符合条件的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('.'); } } result.add(ipAddr.toString()); } return; } // 如果还没有找到4段IP地址，字符串就曾经遍历完了，则提前退出 if (segStart == s.length()) { return; } // 因为不能有前导0，如果以后数字为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; } } } public static void main(String[] args) { for (String restoreIpAddress : restoreIpAddresses("101023")) { System.out.println(restoreIpAddress); } }}【每日寄语】 人不能让本人吃的太饱，当你肚子饿的时候就想和他人争，所以我常常告诫本人不能够让本人吃的太饱，肯定要进来争。