LeetCode_85_RestoreIPAddresses


1. question: 复原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 中的任何数字。你可以按 任何 顺序返回答案。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/restore-ip-addresses

示例 1:

1
2
输入:s = "25525511135"
输出:["255.255.11.135","255.255.111.35"]

示例 2:

1
2
输入:s = "0000"
输出:["0.0.0.0"]

示例 3:

1
2
输入:s = "101023"
输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示:

1
2
1 <= s.length <= 20
s 仅由数字组成

2. answers

这道题和分割回文串类似。只不过这道题限制了将字符串分割成4个子串。并且限制了每个子串的数值大小。主要有如下要求:

  1. 每个数字不能大于255,即限制了每个数字的长度最多为3位,即每个数字最多有三个选择。
  2. 每个数字不能以0开头。
  3. 4个数字必须将字符串完全用完。

所以,递归的终止条件是生成了4个数字,且字符串遍历完。代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
public class Solution_0084 {

// 保存最终结果
public List<String> result = new ArrayList<>();

// // 保存生成的IP地址
// StringBuilder sb = new StringBuilder(); // 注意,此处不能使用成员变量,因为这样做会使得不同数字之间覆盖,

// 保存生成的IP地址(4位数字)
public LinkedList<String> ip = new LinkedList<>();

public void generateIP(char[] chars, int startIndex) {

// 注意,递归终止条件
// 生成四位数字。
if(ip.size() == 4) {

// 如果没有遍历完完数组,就不将结果加入。
if(startIndex == chars.length) {

// 拼接IP
StringBuilder sbs = new StringBuilder();
for(String str: ip) {
sbs.append(str).append(".");
}

sbs.deleteCharAt(sbs.length() - 1);
result.add(sbs.toString());
}

return;
}


// 每个数有如下选择,注意,一个数字最多有三种选择。即限制了最多三位数
int endIndex = Math.min(startIndex + 2, chars.length - 1);
// 保存本数字
StringBuilder sb = new StringBuilder();
for (int i = startIndex; i <= endIndex; i++) {

// 生成本数
// 判断本数是否满足要求,如不满足,继续生成

// 1. 形成新数字,并判断是否满足要求
sb.append(chars[i]);

// 2. 判断是否是0开头,如果是还没生成数字,但是第一个字符却是0,显然,是上一个数字切割不合理。
// 但是要注意,如果只有一个数字,并且是0,是可以的。
if(sb.length() > 1 && sb.charAt(0) == '0') return;

// 3 因为如果当前数字已经大于255了,说明本选择已经没办法再满足了,因为最多是三位数,并且下次只能是4位数了。
// 但是因为外层for循环已经限制了三位数,所以这里continue和return的效果是一样的。
if(Integer.parseInt(sb.toString()) > 255) return;

// 此时生成了满足要求的数字
ip.add(sb.toString());

// 3. 此时数字一定满足要求。递归下一位数字
generateIP(chars, i + 1);

// 回溯,删除最后形成的数字
ip.removeLast();
// 此处无需将sb清空,因为如果1满足了,后续12可能还满足。只有当sb中的数字大于255了,才开始清空。

}

}

public List<String> restoreIpAddresses(String s) {

if(s.length() >= 4)
generateIP(s.toCharArray(), 0);

return result;
}

public static void main(String[] args) {

// String str = "25525511135";
// String str = "0000";
// String str = "101023";
String str = "1";

Solution_0084 s = new Solution_0084();

List<String> strings = s.restoreIpAddresses(str);

for(String strs: strings){
System.out.println(strs);
}

}
}

3. 备注

参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)代码随想录 (programmercarl.com)


文章作者: 浮云
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
  目录