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.25511135
2.5.52.5511135
2.5.525.511135
2.5.5255.11135
2.5.52551.1135
2.5.525511.135
2.5.5255111.35
2.5.52551113.5
2.55.2.5511135
2.55.25.511135
2.55.255.11135
2.55.2551.1135
2.55.25511.135
2.55.255111.35
2.55.2551113.5
2.552.5.511135
2.552.55.11135
2.552.551.1135
2.552.5511.135
2.552.55111.35
2.552.551113.5
2.5525.5.11135
2.5525.51.1135
2.5525.511.135
2.5525.5111.35
2.5525.51113.5
2.55255.1.1135
2.55255.11.135
2.55255.111.35
2.55255.1113.5
2.552551.1.135
2.552551.11.35
2.552551.113.5
2.5525511.1.35
2.5525511.13.5
2.55255111.3.5
25.5.2.5511135
25.5.25.511135
25.5.255.11135
25.5.2551.1135
25.5.25511.135
25.5.255111.35
25.5.2551113.5
25.52.5.511135
25.52.55.11135
25.52.551.1135
25.52.5511.135
25.52.55111.35
25.52.551113.5
25.525.5.11135
25.525.51.1135
25.525.511.135
25.525.5111.35
25.525.51113.5
25.5255.1.1135
25.5255.11.135
25.5255.111.35
25.5255.1113.5
25.52551.1.135
25.52551.11.35
25.52551.113.5
25.525511.1.35
25.525511.13.5
25.5255111.3.5
255.2.5.511135
255.2.55.11135
255.2.551.1135
255.2.5511.135
255.2.55111.35
255.2.551113.5
255.25.5.11135
255.25.51.1135
255.25.511.135
255.25.5111.35
255.25.51113.5
255.255.1.1135
255.255.11.135
255.255.111.35
255.255.1113.5
255.2551.1.135
255.2551.11.35
255.2551.113.5
255.25511.1.35
255.25511.13.5
255.255111.3.5
2552.5.5.11135
2552.5.51.1135
2552.5.511.135
2552.5.5111.35
2552.5.51113.5
2552.55.1.1135
2552.55.11.135
2552.55.111.35
2552.55.1113.5
2552.551.1.135
2552.551.11.35
2552.551.113.5
2552.5511.1.35
2552.5511.13.5
2552.55111.3.5
25525.5.1.1135
25525.5.11.135
25525.5.111.35
25525.5.1113.5
25525.51.1.135
25525.51.11.35
25525.51.113.5
25525.511.1.35
25525.511.13.5
25525.5111.3.5
255255.1.1.135
255255.1.11.35
255255.1.113.5
255255.11.1.35
255255.11.13.5
255255.111.3.5
2552551.1.1.35
2552551.1.13.5
2552551.11.3.5
25525511.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.135
255.255.111.35

时间复杂度

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

最终实现

Java实现

class Solution {
        public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12) {
            return new ArrayList<>();
        }
        List<String> candidates = new ArrayList<>();
        // Step 1. Select all probable slots
        List<Position> 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地址这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！