# 题目

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example: Given “25525511135”,

return [“255.255.11.135”, “255.255.111.35”]. (Order does not matter) 给你一个只包含数字的字符串，把其中的数字重组为可能的ip地址组合，不能改变原先字符的顺序。

# 解题思路

```//下限，3为每个字段最多的长度，下限不可能小于1
int lower = 字符串总长度 - 剩余字段个数 * 3 > 1 ? 字符串总长度 - 剩余字段个数 * 3;
//上限,1为每个字段至少的长度，上限不可能大于3
int upper = 字符串总长度 - 剩余字段个数 * 1 < 3 ? 字符串总长度 - 剩余字段个数 * 1  : 3;```

```public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
if (s.length() > 12 || s.length() < 4) return res;
ipHelper(s, res, 3, new ArrayList<>());
return res;
}

/**
*
* @param s 用来分析的字符串，是上一次去除选中字符串的结果
* @param res 存放结果的集合
* @param count 统计现在计算到第几个字段了
* @param list 用来把不同的字符串组合成一个ip，同时也为了结合count方便删除不满足条件的字段
*/
private void ipHelper(String s, List<String> res, int count, ArrayList<Integer> list) {
if (count == 0) {
int val = Integer.valueOf(s);
if (s.length() > 1 && s.startsWith("0")) {
return;
} else if (val >= 0 && val <= 255) {
StringBuilder sb = new StringBuilder();
for (int k : list) {
sb.append(".").append(k);
}
list.remove(3 - count);
return;
} else {
return;
}
}
//下限
int lower = s.length() - count * 3 > 1 ? s.length() - count * 3 : 1;
//上限
int upper = s.length() - count < 3 ? s.length() - count : 3;
if (lower > upper) {
return;
}
for (int i = lower; i <= upper; i++) {
String tmpString = s.substring(0, i);
int val = Integer.valueOf(tmpString);
if (i > 1 && tmpString.startsWith("0")) {
return;
} else if (val >= 0 && val <= 255) {
} else
return;
ipHelper(s.substring(i), res, count - 1, list);
list.remove(3 - count);
}

}```

0 条评论

• ### LeetCode242 Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s...

• ### LeetCode387 First Unique Character in a String

Given a string, find the first non-repeating character in it and return it’s ind...

• ### LeetCode409 Longest Palindrome

Given a string which consists of lowercase or uppercase letters, find the length...

• ### 聊聊hystrix的queueSizeRejectionThreshold参数

本文主要研究一下hystrix的queueSizeRejectionThreshold参数

• ### LeetCode题解—斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

• ### 分享|C# 中yield关键字解析

前段时间了解到yield关键字，一直觉得还不错。今天给大家分享一下yield关键字的用法。yield return 返回集合不是一次性返回所有集合元素，而是...

• ### C# 中yield关键字解析

前段时间了解到yield关键字，一直觉得还不错。今天给大家分享一下yield关键字的用法。yield return 返回集合不是一次性返回所有集合元素，而是...

• ### SpringBoot+SpringSecurity处理Ajax登录请求

最近在项目中遇到了这样一个问题：前后端分离，前端用Vue来做，所有的数据请求都使用vue-resource，没有使用表单，因此数据交互都是使用JSON，后台使用...

• ### SpringBoot+SpringSecurity处理Ajax登录请求

最近在项目中遇到了这样一个问题：前后端分离，前端用Vue来做，所有的数据请求都使用vue-resource，没有使用表单，因此数据交互都是使用JSON，后台使用...

• ### 经典算法面试题目-替换字符串的内容（1.5）

Write a method to replace all spaces in a string with ‘%20’.