LeetCode93. 复原 IP 地址
题目描述
/**
*
* 给定一个只包含数字的字符串，用以表示一个 IP 地址，
* 返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
* <p>
* 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），
* 整数之间用 ‘.‘ 分隔。
* <p>
* 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，
* 但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
*
*/
思路分析
- 复原IP地址，即给定一个数字字符串，按照IP地址规则将其复原为多个满足条件的IP地址
- 很容易想到递归 + 回溯的方法
- 定义一个大小为4 的全局数组，用于保存IP地址的每一段，因此还需要一个索引记录是那一段
- 使用深度优先的方式，即遍历字符串，选择一个满足条件的数字字符串作为IP地址的第一段，等条件不满足或找到满足的后再回溯寻找第一个满足的其他字符串，然后从未选择的字符串开始，依次再选择第二段，第二段仍然有很多选择，先选择一个，等条件不满足或找到满足的后再回溯，直至选择到最后一段
- 不断的递归 + 回溯，直到找到所有满足的或者筛选掉所有不满足的
- 递归结束的条件为保存每一段的数组中都存储了满足格式的字符串，并且字符串全部遍历结束，说明找到满足IP递归规则的，则结束
- 或者数组已满，但是字符串还没有遍历完，说明不满足
- 还要考虑字符串的某一位为零的情况，则直接将零作为单独的一段即可
- 其他正常情况递归+回溯即可
- 源码见下
源码及分析
//表示总共将字符串分为4段
static final int SEG_COUNT = 4;
//创建集合保存结果
List<String> list = new ArrayList<>();
//创建数组保存每一段的元素
int[] segments = new int[SEG_COUNT];
public List<String> restoreIpAddresses(String s) {
dfs(s,0,0);
return list;
}
/**
* 从字符串s的start位置开始寻找下一段的元素
*
* @param s 字符串
* @param seg 表示第几段
* @param start 下一段开始位置索引
*/
public void dfs(String s, int seg, int start) {
//如果找到了四段ip并且遍历完了字符串，那么就是一种答案
if (seg == SEG_COUNT){
if (start == s.length()){
//走到这一步说明segments数组中已经存在一个满足要求的答案，将其拼接转成字符串即可
StringBuffer ipAddress = new StringBuffer();
for (int i = 0; i < SEG_COUNT; i++) {
//拼接字符串
ipAddress.append(segments[i]);
//拼接 .
if (i != SEG_COUNT - 1){
ipAddress.append(‘.‘);
}
}
//将拼接后的结果添加到集合中
list.add(ipAddress.toString());
}
//找到一个后继续回溯
return;
}
//如果还没找到4段IP就已经遍历完了字符串，那么提前回溯
if (start == s.length()){
return;
}
//由于前导不能为零，如果遇到零，只能将0作为这一段的ip
if (s.charAt(start) == ‘0‘) {
segments[seg] = 0;
dfs(s, seg + 1, start + 1);
}
//正常情况下，枚举每一种可能性并递归
//定义变量保存每一段的结果
int address = 0;
//从start开始遍历，直到遍历完字符串
for (int i = start; i < s.length(); i++) {
//先将每一段的字符转为数字
address = address * 10 + (s.charAt(i) - ‘0‘);
//判断当前段的地址是否满足条件，如果满足，则递归判断下一段，否则结束
if (address > 0 && address <= 255) {
segments[seg] = address;
dfs(s, seg + 1, i + 1);
}else {
break;
}
}
}
LeetCode93. 复原 IP 地址