leetcode 93. 复原IP地址
题目：93. 复原IP地址
给定一个只包含数字的字符串，复原它并返回所有可能的 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 地址。
示例1:
输入：s = “25525511135”
输出：[“255.255.11.135”,”255.255.111.35”]
示例2:
输入：s = “0000”
输出：[“0.0.0.0”]
示例3:
输入：s = “1111”
输出：[“1.1.1.1”]
示例4:
输入：s = “010010”
输出：[“0.10.0.10”,”0.100.1.0”]
示例5:
输入：s = “101023”
输出：[“1.0.10.23”,”1.0.102.3”,”10.1.0.23”,”10.10.2.3”,”101.0.2.3”]
说明:
- 0 <= s.length <= 3000
- s 仅由数字组成
方法：Backtracking（回溯）
思路：Backtracking（回溯），由于IP地址为4段，每一段最多只有3位数，所以回溯的递归层次为4，每层有3钟情况。
运行数据：执行用时：4 ms，内存消耗：40 MB
复杂度分析：
- 时间复杂度：O(1)，回溯递归的时间复杂度为O(3^4)。
- 空间复杂度：O(1)，回溯递归的栈开销O(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
|
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<String>();
if (s == null || s.length() == 0) {
return result;
}
restore(0, new StringBuilder(), s, result);
return result;
}
private void restore(int t, StringBuilder prefix, String s, List<String> result) {
if (t == 4 || s.length() == 0) {
if (t == 4 && s.length() == 0) {
result.add(prefix.toString());
}
return ;
}
for (int i = 0; i < s.length() && i <= 2; i++) {
if (i != 0 && s.charAt(0) == '0') {
break;
}
String tempString = s.substring(0, i + 1);
if (Integer.valueOf(tempString) <= 255) {
if (prefix.length() != 0) {
tempString = "." + tempString;
}
prefix.append(tempString);
restore(t + 1, prefix, s.substring(i + 1), result);
prefix.delete(prefix.length() - tempString.length(), prefix.length());
}
}
}
|
学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。
才疏学浅，若有错误或不当之处，可批评指正，还请见谅！
