原创牛客网算法—名企高频面试题143题(16)
- 作者: 达?矢抾哆拉?
- 来源: 51数据库
- 2021-10-30
93. 复原IP地址
class Solution {
List<String> res = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
List<String> segment = new ArrayList<>();
//开始搜索
dfs(s, 0, segment);
return res;
}
private void dfs(String s, int start, List<String> segment) {
if (start == s.length()) {
if (segment.size() == 4) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < segment.size(); i++) {
sb.append(segment.get(i));
if (i != segment.size() - 1) sb.append('.');
}
res.add(sb.toString());
}
return;
} else {
if (segment.size() >= 4) return;
for (int i = start; i < s.length() && i < start + 3; i++) {
String str = s.substring(start, i + 1);
if (str.charAt(0) == '0' && str.length() > 1) break;
int num = Integer.parseInt(str);
if (num >= 0 && num <= 255) {
segment.add(str);
dfs(s, i + 1, segment);
segment.remove(segment.size() - 1);
} else {
break;
}
}
}
}
}
468. 验证IP地址
?
推荐阅读