友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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"]
提示：
-
1 <= s.length <= 20 -
s仅由数字组成
思路分析
使用回溯，每次做一次字符串切割，如果切割的字符串符合 IP 的大小值，则前进一步，直到把字符串切割完毕并且正好切割四份。
-
一刷
-
二刷
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
/**
* Runtime: 2 ms, faster than 88.51% of Java online submissions for Restore IP Addresses.
* Memory Usage: 38.4 MB, less than 30.23% of Java online submissions for Restore IP Addresses.
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-02-06 10:00
*/
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<>();
backtrack(s, 0, new ArrayDeque<>(), result);
return result;
}
private void backtrack(String s, int start, Deque<String> current, List<String> result) {
if (start == s.length() && current.size() == 4) {
result.add(String.join(".", current));
return;
}
for (int i = start + 1; i <= s.length() && i <= start + 3 && current.size() < 4; i++) {
String substring = s.substring(start, i);
if (substring.length() > 1 && substring.charAt(0) == '0') {
continue;
}
int num = Integer.parseInt(substring);
if (0 <= num && num <= 255) {
current.addLast(substring);
backtrack(s, i, current, result);
current.removeLast();
}
}
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2020-02-06 10:00
*/
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<>();
backtrack(s, result, new ArrayList<>(4), 0);
return result;
}
private void backtrack(String s, List<String> result, List<String> path, int index) {
if (path.size() == 4) {
if (index == s.length()) {
result.add(String.join(".", path));
}
return;
}
for (int i = 1; i <= 3; i++) {
int end = index + i;
if (end > s.length()) {
break;
}
String nums = s.substring(index, end);
if (Integer.parseInt(nums) > 255) {
break;
}
path.add(nums);
backtrack(s, result, path, end);
path.removeLast();
// 如果起始字符是 0，则只处理 0 这一种情况，不允许出现 01 等情况
if (s.charAt(index) == '0') {
break;
}
}
}