java怎么还原IP地址

这篇文章主要讲解了"java怎么还原IP地址"，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习"java怎么还原IP地址"吧！

Example 1:

Input: s = "25525511135"Output: ["255.255.11.135","255.255.111.35"]

Example 2:

Input: s = "0000"Output: ["0.0.0.0"]

Example 3:

Input: s = "1111"Output: ["1.1.1.1"]

Example 4:

Input: s = "010010"Output: ["0.10.0.10","0.100.1.0"]

Example 5:

Input: s = "101023"Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Constraints:

• 0 <= s.length <= 3000

• s consists of digits only.

解题思路

首先既然要验证的是一个IP地址，那就意味着这个给定的字符串一定不能超过12个字符，因为如果超过12个字符就不可能是IP地址。在此基础上，这个给定的字符串最多只有12个字符，要让一个字符串对应的可能的IP地址，就要穷举出所有的情况，然后逐个验证。穷举的方式相当于往字符之间的（顶多）11个空位中添加3个点，一共有C^3_11种加点的方式。例如，25525511135的所有可能情况如下所示，只要剔除不可能的情况即可：

2.5.5.255111352.5.52.55111352.5.525.5111352.5.5255.111352.5.52551.11352.5.525511.1352.5.5255111.352.5.52551113.52.55.2.55111352.55.25.5111352.55.255.111352.55.2551.11352.55.25511.1352.55.255111.352.55.2551113.52.552.5.5111352.552.55.111352.552.551.11352.552.5511.1352.552.55111.352.552.551113.52.5525.5.111352.5525.51.11352.5525.511.1352.5525.5111.352.5525.51113.52.55255.1.11352.55255.11.1352.55255.111.352.55255.1113.52.552551.1.1352.552551.11.352.552551.113.52.5525511.1.352.5525511.13.52.55255111.3.525.5.2.551113525.5.25.51113525.5.255.1113525.5.2551.113525.5.25511.13525.5.255111.3525.5.2551113.525.52.5.51113525.52.55.1113525.52.551.113525.52.5511.13525.52.55111.3525.52.551113.525.525.5.1113525.525.51.113525.525.511.13525.525.5111.3525.525.51113.525.5255.1.113525.5255.11.13525.5255.111.3525.5255.1113.525.52551.1.13525.52551.11.3525.52551.113.525.525511.1.3525.525511.13.525.5255111.3.5255.2.5.511135255.2.55.11135255.2.551.1135255.2.5511.135255.2.55111.35255.2.551113.5255.25.5.11135255.25.51.1135255.25.511.135255.25.5111.35255.25.51113.5255.255.1.1135255.255.11.135255.255.111.35255.255.1113.5255.2551.1.135255.2551.11.35255.2551.113.5255.25511.1.35255.25511.13.5255.255111.3.52552.5.5.111352552.5.51.11352552.5.511.1352552.5.5111.352552.5.51113.52552.55.1.11352552.55.11.1352552.55.111.352552.55.1113.52552.551.1.1352552.551.11.352552.551.113.52552.5511.1.352552.5511.13.52552.55111.3.525525.5.1.113525525.5.11.13525525.5.111.3525525.5.1113.525525.51.1.13525525.51.11.3525525.51.113.525525.511.1.3525525.511.13.525525.5111.3.5255255.1.1.135255255.1.11.35255255.1.113.5255255.11.1.35255255.11.13.5255255.111.3.52552551.1.1.352552551.1.13.52552551.11.3.525525511.1.3.5

针对每种情况c，将它分割为4个部分，比如2.5.5.25511135被分割为2、5、5、25511135，接下来对每个部分做判断。设其中一个部分的字符串为x，则只需要判断它是否满足以下两个条件，如果不满足则c这种情况就不是合法IP地址（在这个例子中是2.5.5.25511135）：

1）x不能大于255；

2）x如果不等于0的话，它的第一个字符不能为0，比如02这种就是不满足的。

只有4个部分（2、5、5、25511135）都满足了上述两个条件，才算是合法的IP地址。对于上面的例子而言，所有情况里面就只有以下两个才是合法的IP地址：

255.255.11.135255.255.111.35

时间复杂度

无论初始给定的字符串长度是多少，一共最多只有C^3_11=165种加点的方式，所以时间复杂度为O(165)=O(1)

最终实现

Java实现

class Solution {        public List restoreIpAddresses(String s) {        if (s.length() > 12) {            return new ArrayList<>();        }        List candidates = new ArrayList<>();        // Step 1. Select all probable slots        List positions = new ArrayList<>();        for (int i = 1; i < s.length(); i++) {            for (int j = i + 1; j < s.length(); j++) {                for (int k = j + 1; k < s.length(); k++) {                    Position pos = new Position(i, j, k);                    positions.add(pos);                }            }        }        // Step 2. Add dot to the given string        for (Position pos : positions) {            StringBuffer buffer = new StringBuffer(s);            buffer.insert(pos.getZ(), ".");            buffer.insert(pos.getY(), ".");            buffer.insert(pos.getX(), ".");            String candidate = buffer.toString();            if (isValidIpAddress(candidate)) {                candidates.add(candidate);            }        }        return candidates;    }        private boolean isValidIpAddress(String ipAddress) {        String[] blocks = ipAddress.split("\\.");        for (String block : blocks) {            if (Integer.valueOf(block) > 255) {                return false;            }            if (block.startsWith("0") && block.length() != 1) {                return false;            }        }        return true;    }    static class Position {        private int x;        private int y;        private int z;        public Position(int x, int y, int z) {            this.x = x;            this.y = y;            this.z = z;        }        public int getX() {            return x;        }        public void setX(int x) {            this.x = x;        }        public int getY() {            return y;        }        public void setY(int y) {            this.y = y;        }        public int getZ() {            return z;        }        public void setZ(int z) {            this.z = z;        }    }}

感谢各位的阅读，以上就是"java怎么还原IP地址"的内容了，经过本文的学习后，相信大家对java怎么还原IP地址这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是，小编将为大家推送更多相关知识点的文章，欢迎关注！