🚩传送门：牛客题目

题目

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间，且不能含有前导 0），整数之间用 '.' 分隔。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按 任何顺序 返回答案。

例如： "0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址

示例 1：

输入：s = “25525511135” 输出：[“255.255.11.135”,”255.255.111.35”]

示例 2：

输入：s = “0000” 输出：[“0.0.0.0”]

解题思路：回溯

我们需要找出所有可能复原出的 IP 地址，因此可以考虑使用回溯的方法，对所有可能的字符串分隔方式进行搜索，并筛选出满足要求的作为答案。

特别地，由于 IP 地址的每一段不能有前导零，因此如果 [NC]20. 数字字符串转化成IP地址 - 图1 等于字符 0，那么 IP 地址的第 segId 段只能为 0，需要作为特殊情况进行考虑。

复杂度分析

我们用 [NC]20. 数字字符串转化成IP地址 - 图2 表示 IP 地址的段数。

时间复杂度：[NC]20. 数字字符串转化成IP地址 - 图3

  1.   - 由于 IP 地址的每一段的位数不会超过 **3**，因此在递归的每一层，我们最多只会深入到下一层的 **3** 种情况。由于 ![](https://cdn.nlark.com/yuque/__latex/c69c3cc90ce7a9ae46619f842321a87c.svg#card=math&code=%5Csmall%20%5Ctext%7BSEG_COUNT%7D%20%3D%204&id=phqT6) ，对应递归最大层数，所以递归本身时间复杂度为 ![](https://cdn.nlark.com/yuque/__latex/9cd864849f75790ee99dc010cb04a384.svg#card=math&code=O%283%5E%5Ctext%7BSEG_COUNT%7D%29&height=23&id=UmY5Y)。如果我们复原出了一种满足题目要求的 IP 地址，那么需要 ![](https://cdn.nlark.com/yuque/__latex/a38547bfebdd3f0eade7b89765961592.svg#card=math&code=O%28%7Cs%7C%29&height=23&id=SDmwi) 的时间将其加入答案数组中，因此总时间复杂度为 ![](https://cdn.nlark.com/yuque/__latex/a17183be3ebfa9d2d5715563c380ac33.svg#card=math&code=O%283%5E%5Ctext%7BSEG_COUNT%7D%20%5Ctimes%20%7Cs%7C%29&height=23&id=ui6r3)。

空间复杂度：[NC]20. 数字字符串转化成IP地址 - 图4

  1.   - 这里只计入除了用来存储答案数组以外的额外空间复杂度。递归使用的空间与递归的最大深度 ![](https://cdn.nlark.com/yuque/__latex/1f3e99bb40a80f23618711718dd66d85.svg#card=math&code=%5Csmall%20%5Ctext%7BSEG_COUNT%7D&height=23&id=ze7p5) 成正比。并且在上面的代码中，我们只额外使用了长度为 ![](https://cdn.nlark.com/yuque/__latex/1f3e99bb40a80f23618711718dd66d85.svg#card=math&code=%5Csmall%20%5Ctext%7BSEG_COUNT%7D&height=23&id=mvv51) 的数组 **segments **存储已经搜索过的 IP 地址，因此空间复杂度为 ![](https://cdn.nlark.com/yuque/__latex/5c78de4b05f7d2f661c17033737a2298.svg#card=math&code=%5Csmall%20O%28%5Ctext%7BSEG_COUNT%7D%29&height=23&id=PJwxo)。

官方代码

  1. class Solution {
  2.     static final int SEG_COUNT = 4;                    // Ip 字段总长度
  3.     List<String> ans = new ArrayList<String>();        // 总结果集
  4.     int[] segments = new int[SEG_COUNT];            // 临时结果集
  6.     public List<String> restoreIpAddresses(String s) {
  7.         dfs(s, 0, 0);
  8.         return ans;
  9.     }
  11.     public void dfs(String s, int segId, int segStart) {
  12.         // 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
  13.         if (segId == SEG_COUNT) {
  14.             if (segStart == s.length()) {
  15.                 StringBuffer ipAddr = new StringBuffer();
  16.                 for (int i = 0; i < SEG_COUNT; ++i) {
  17.                     ipAddr.append(segments[i]).append('.');
  18.                 }
  19.                 ipAddr.deleteCharAt(ipAddr.length()-1);    // 删除末尾的 '.'
  20.                 ans.add(ipAddr.toString());
  21.             }
  22.             return;
  23.         }
  25.         // 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
  26.         if (segStart == s.length()) {
  27.             return;
  28.         }
  30.         // 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
  31.         if (s.charAt(segStart) == '0') {
  32.             segments[segId] = 0;
  33.             dfs(s, segId + 1, segStart + 1);
  34.         }
  36.         // 一般情况，枚举每一种可能性并递归
  37.         int addr = 0;
  38.         for (int segEnd = segStart; segEnd < s.length(); ++segEnd) {
  39.             addr = addr * 10 + (s.charAt(segEnd) - '0');
  40.             if (addr > 0 && addr <= 0xFF) {
  41.                 segments[segId] = addr;
  42.                 dfs(s, segId + 1, segEnd + 1);
  43.             } else {
  44.                 break;
  45.             }
  46.         }
  47.     }
  48. }