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地址這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！