【面试高频题】难度 2/5，回溯算法经典运用

题目描述

这是 LeetCode 上的 ​​93. 复原 IP 地址​​ ，难度为 中等。

Tag : 「回溯」、「DFS」

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

例如：​​"0.1.2.201"​​​ 和 ​​"192.168.1.1"​​​ 是 有效 ​​IP​​​ 地址，但是 ​​"0.011.255.245"​​​、​​"192.168.1.312"​​​ 和 ​​"[email protected]"​​​ 是 无效 ​​IP​​ 地址。

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

示例 1：

输入：s = "25525511135"

输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"

输出：["0.0.0.0"]

示例 3：

输入：s = "101023"

输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

• 
• ​​s​​ 仅由数字组成

回溯算法

和 ​​131. 分割回文串​​ 一样，同样是一道求所有方案的题目，只能是没有太多优化的「爆搜」做法。

设计递归函数为 ​​void dfs(int idx, int n, List<Integer> cur)​​​，其中 ​​idx​​​ 和 ​​n​​​ 分别代表当前处理字符串 ​​s​​​ 的哪个位置，以及字符串 ​​s​​​ 的总长度，而 ​​cur​​​ 的则是代表子串

用题目样例 ​​s = "25525511135"​​​ 作为