93. 复原 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 地址。
给定一个只包含数字的字符串 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”]
思考
这个题也是一个明显的回溯问题。
每一次截取该层的startIndex - i 的。
所以共截取四层。结束条件为:
// 如果深度为 4
if (list.size()==4){
if(templength==s.length()){
lists.add(list.get(0)+"."+list.get(1)+"."+list.get(2)+"."+list.get(3));
}
return;
}
每一层 从startIndex开始，递增三个数，代表了一层的IP地址。
- 该层的IP地址大小不能大于255
- 该层的IP地址大小不能以0开头
package 力扣;
import java.util.ArrayList;
import java.util.List;
/**
* @author yyq
* @create 2022-05-03 15:43
*/
public class leetcode93 {
public static void main(String[] args) {
leetcode93 leetcode93=new leetcode93();
List<String> list = leetcode93.restoreIpAddresses("101023");
System.out.println(list);
}
public List<String> restoreIpAddresses(String s) {
List<String> lists = new ArrayList<>();
if(s.length()<4||s.length()>12){
return lists;
}
// 用来保存当前list中字符串的总长度
int templength = 0;
// 该层起始坐标
int startIndex = 0;
int deep = 1;
List<String> list=new ArrayList<>();
backTracking(startIndex,s,templength,deep,list,lists);
return lists;
}
private void backTracking(int startIndex, String s, int templength,int deep, List<String> list, List<String> lists) {
// 如果深度为 4
if (list.size()==4){
if(templength==s.length()){
lists.add(list.get(0)+"."+list.get(1)+"."+list.get(2)+"."+list.get(3));
}
return;
}
// 每一次 横向遍历的范围 不能超过startIndex 3，超过肯定不符合了。
// 每次获取 startIndex 到 i 范围的数
for (int i=startIndex;i<startIndex+3&&i<s.length();i++){
// 如果这个数大于 255 肯定不符合IP地址规则
if(new Integer(s.substring(startIndex,i+1))>255) return;
String substring = s.substring(startIndex, i + 1);
if(substring.length()>1){
// 不能包含前置0
if(substring.charAt(0)=='0') return;
}
list.add(substring);
templength = templength + (i + 1 - startIndex);
deep++;
backTracking(i+1,s,templength,deep,list,lists);
deep--;
templength = templength - (i + 1 - startIndex);
list.remove(list.size()-1);
}
}
}
