Java算法（数字字符串中复原所有可能的IP地址）

题目：

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 ‘.’ 分隔。

示例:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"] 

思路

每个整数位于 0 到 255 之间组成，所以对于第一个片段的选取，有三种情况：
（1）选 “2” 这一个数字
（2）选 “25” 这两个数字
（3）选 “255” 这三个数字
对于第一种选择，选第二个片段的时候又有三种情况，分别是选一个数字，选两个数字，选三个数字，典型的 dfs 。

代码：

import java.util.ArrayList; import java.util.List; public class Solution { private static int SEG_COUNT = 4; private static List<String> ans = new ArrayList<>(); private static int[] segments = new int[SEG_COUNT]; public static void main(String[] args) { String s= "25525511135"; System.out.println(restoreIpAddresses(s)); } public static List<String> restoreIpAddresses(String s) { segments = new int[SEG_COUNT]; dfs(s, 0, 0); return ans; } private static void dfs(String s, int segId, int segStart) { // 出口处理稍稍复杂一些。 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; } if(segStart == s.length()) return; 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; } } } } 

本文地址：https://blog.csdn.net/qq_36565596/article/details/107891137