93. 复原 IP 地址
题目链接
https://leetcode.cn/problems/restore-ip-addresses/
相关算法
回溯
题目描述
有效 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 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
数据范围：
1 <= s.length <= 20s仅由数字组成
解题思路
本题显然也可以使用回溯法来做，而比起之前不断构造新的路径的思路，这题显然尝试不断向原字符串中插入 '.' 会更加简便，所以考虑使用 StringBuilder 对原字符串进行存储，便于后续编辑操作。我们可以在每次尝试插入前，先判断插入后分割出来的片段是否合法，大致需要判断的内容如下：
- 片段长度，如果片段长度大于
3，则表示的数值大小必定大于255 - 数值大小：
- 如果片段长度小于
3，则合法，因为数值必定是处于0到255的区间内 - 如果片段长度等于
3，则需要判断当前数值与255的大小关系
- 如果片段长度小于
于是有以下代码：
private boolean isValid(int start, int end, StringBuilder sb) {if (start > end || end - start >= 3) {return false;}if (sb.charAt(start) == '0' && start != end) {return false;}if (end - start == 2) {int num = 0;for (int i = start; i <= end; i++) {num = 10 * num + (sb.charAt(i) - '0');}return num <= 255;}return true;
}
在回溯的递归函数中，我们需要考虑传入哪些参数，首先，暂存的 StringBuilder 对象是需要的，然后是当前加点切割的起始点 start。而为了便于终止回溯，我们再传入一个 count 用于记录当前已经添加了多少个 '.'，接下来，就按照回溯的思路来写就行了。
完整代码
class Solution {List<String> ans = new ArrayList<>();public List<String> restoreIpAddresses(String s) {if (s.length() < 4 || s.length() > 12) {return ans;}StringBuilder temp = new StringBuilder(s);backtrace(0, 0, temp);return ans;}private void backtrace(int start, int count, StringBuilder sb) {if (count == 3 && isValid(start, sb.length() - 1, sb)) {ans.add(sb.toString());return;}for (int i = start; i < sb.length(); i++) {if (isValid(start, i, sb)) {sb.insert(i + 1, '.');backtrace(i + 2, count + 1, sb);sb.deleteCharAt(i + 1);}}}private boolean isValid(int start, int end, StringBuilder sb) {if (start > end || end - start >= 3) {return false;}if (sb.charAt(start) == '0' && start != end) {return false;}if (end - start == 2) {int num = 0;for (int i = start; i <= end; i++) {num = 10 * num + (sb.charAt(i) - '0');}return num <= 255;}return true;}
}
