友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
93. Restore IP Addresses
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example:
Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"]
参考资料
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example:
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
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
/**
* 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.
*/
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();
}
}
}