点击上方蓝字设为星标
下面开始今天的学习～力扣468. 验证 IP 地址(点击文末阅读原文查看题目)题目描述
编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址。
IPv4地址由十进制数和点来表示，每个地址包含 4 个十进制数，其范围为0- 255，用(".")分割。比如，172.16.254.1；
同时，IPv4 地址内的数不会以 0 开头。比如，地址 172.16.254.01 是不合法的。
IPv6地址由 8 组 16 进制的数字来表示，每组表示 16 比特。这些组数字通过(":")分割。比如, 2001:0db8:85a3:0000:0000:8a2e:0370:7334 是一个有效的地址。而且，我们可以加入一些以 0 开头的数字，字母可以使用大写，也可以是小写。所以，2001:db8:85a3:0:0:8A2E:0370:7334 也是一个有效的 IPv6 address 地址 (即，忽略 0 开头，忽略大小写)。
然而，我们不能因为某个组的值为 0，而使用一个空的组，以至于出现 (::)的情况。比如，2001:0db8:85a3::8A2E:0370:7334 是无效的 IPv6 地址。
同时，在 IPv6 地址中，多余的0也是不被允许的。比如，02001:0db8:85a3:0000:0000:8a2e:0370:7334 是无效的。
说明:你可以认为给定的字符串里没有空格或者其他特殊字符。
示例 1:
输入: "172.16.254.1"输出: "IPv4"解释: 这是一个有效的 IPv4 地址, 所以返回 "IPv4"。
示例 2:
输入: "2001:0db8:85a3:0:0:8A2E:0370:7334"输出: "IPv6"解释:这是一个有效的IPv6地址,所以返回"IPv6"。
示例 3:
输入: "256.256.256.256"输出: "Neither"解释: 这个地址既不是 IPv4 也不是 IPv6 地址。
解决方案
概述
最直接的方法是使用内置函数和 try/catch 结构检查 IP 地址的正确性：在 Python 中使用 ipaddress，在 Java 中使用 InetAddress 。
Python 实现
from ipaddress import ip_address, IPv6Addressclass Solution: def validIPAddress(self, IP: str) -> str: try: return "IPv6" if type(ip_address(IP)) is IPv6Address else "IPv4" except ValueError:return"Neither"
Java 实现
import .*;class Solution {public String validIPAddress(String IP) {try {return (InetAddress.getByName(IP) instanceof Inet6Address) ? "IPv6": "IPv4"; } catch(Exception e) {} return "Neither"; }}
注意：这两个类都是引用 POSIX -兼容的 inet-addr()解析地址。如果地址带有前导零块，可能会发生错误。
地址的组成可以使十进制，八进制(以 0 开始)，或十六进制(以 0X 开始)。
例如01.01.01.012 是有效的八进制 IP 地址。检查该地址是否有效可以在控制台运行命令 ping 01.01.01.012，八进制地址01.01.01.012 会被转换为对应的十进制地址 1.1.1.10，因此执行 ping 命令不会出错。
该题目指出如果IPv4 地址包含前置 0，则地址是无效的，但其实这不符合真实情况，不过我们仍然需要解决它。
该题目要三种主要解法：
正则表达式，该方法性能不太好。
分治法，效率最高的方法之一。
使用分治法和内置的 try/catch，将字符串转换成整数处理。使用 try/catch 不是一种好的方式，因为 try 块中的代码不会被编译器优化，所以最好不要在面试中使用。
方法一：正则表达式
构造适用该题目的 “IPv4” 地址的正则表达式。注意前面讨论的前置零问题，它不属于 IPv4 地址。
在 Python 中使用原始字符串 r''构造正则表达式：
在 Java 中使用标准字符串构造正则表达式：
现在问题被简化为检查每个块是否正确，每个块的范围为(0, 255)，且不允许有前置零出现。一共有五种情况：
块只包含一位数字，范围是 0 到 9。
块包含两位数字，第一位的范围是 1 到 9，第二位是 0 到 9。
块包含三位数字，且第一位为 1。第二、三位可以是 0 到 9。
块包含三位数字，且第一位为 2，第二位为 0 到 4。那么第三位可以是 0 到 9。
块包含三位数字，且第一位为 2，第二位为 5，那么第三位可以是 0 到 5。
创建包含这 5 种情况的正则表达式。
使用相同逻辑构造匹配 IPv6 地址的正则表达式。
Python 实现
import reclass Solution: chunk_IPv4 = r'([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])' patten_IPv4 = pile(r'^(' + chunk_IPv4 + r'\.){3}' + chunk_IPv4 + r'$') chunk_IPv6 = r'([0-9a-fA-F]{1,4})' patten_IPv6 = pile(r'^(' + chunk_IPv6 + r'\:){7}' + chunk_IPv6 + r'$') def validIPAddress(self, IP: str) -> str:if '.' in IP: return "IPv4" if self.patten_IPv4.match(IP) else "Neither" if ':' in IP: return "IPv6" if self.patten_IPv6.match(IP) else "Neither" return"Neither"
Java 实现
import java.util.regex.Pattern;class Solution {String chunkIPv4 = "([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])"; Pattern pattenIPv4 =pile("^(" + chunkIPv4 + "\\.){3}" + chunkIPv4 + "$"); String chunkIPv6 = "([0-9a-fA-F]{1,4})"; Pattern pattenIPv6 =pile("^(" + chunkIPv6 + "\\:){7}" + chunkIPv6 + "$"); public String validIPAddress(String IP) {if (IP.contains(".")) {return (pattenIPv4.matcher(IP).matches()) ? "IPv4" : "Neither"; } else if (IP.contains(":")) {return (pattenIPv6.matcher(IP).matches()) ? "IPv6" : "Neither"; } return "Neither"; }}
复杂度分析
时间复杂度：O(1)。
空间复杂度：O(1)。
方法二：分治法
思想
IPv4 和 IPv6 地址均是由特定的分界符隔开的字符串组成，并且每个子字符串具有相同格式。
因此，可以将地址分为多个块，然后逐块进行验证。
仅当每个块都有效时，该地址才有效。这种方法称为分治法。
算法
对于 IPv4 地址，通过界定符 . 将地址分为四块；对于 IPv6 地址，通过界定符:将地址分为八块。
对于 IPv4 地址的每一块，检查它们是否在0 - 255 内，且没有前置零。
对于 IPv6 地址的每一块，检查其长度是否为 1 - 4 位的十六进制数。
Python 实现
class Solution: def validate_IPv4(self, IP: str) -> str: nums = IP.split('.') for x in nums: # Validate integer in range (0, 255): # 1. length of chunk is between 1 and 3 if len(x) == 0 or len(x) > 3:return "Neither" # 2. no extra leading zeros # 3. only digits are allowed # 4. less than 255 if x[0] == '0' and len(x) != 1 or not x.isdigit() or int(x) > 255:return "Neither" return "IPv4" def validate_IPv6(self, IP: str) -> str: nums = IP.split(':') hexdigits = '0123456789abcdefABCDEF' for x in nums: # Validate hexadecimal in range (0, 2**16): # 1. at least one and not more than 4 hexdigits in one chunk # 2. only hexdigits are allowed: 0-9, a-f, A-F if len(x) == 0 or len(x) > 4 or not all(c in hexdigits for c in x):return "Neither" return "IPv6" def validIPAddress(self, IP: str) -> str: if IP.count('.') == 3: return self.validate_IPv4(IP) elif IP.count(':') == 7: return self.validate_IPv6(IP) else:return"Neither"
Java 实现
class Solution {public String validateIPv4(String IP) {String[] nums = IP.split("\\.", -1); for (String x : nums) {// Validate integer in range (0, 255):// 1. length of chunk is between 1 and 3if (x.length() == 0 || x.length() > 3) return "Neither";// 2. no extra leading zerosif (x.charAt(0) == '0' && x.length() != 1) return "Neither";// 3. only digits are allowedfor (char ch : x.toCharArray()) {if (! Character.isDigit(ch)) return "Neither";}// 4. less than 255if (Integer.parseInt(x) > 255) return "Neither"; } return "IPv4"; } public String validateIPv6(String IP) {String[] nums = IP.split(":", -1); String hexdigits = "0123456789abcdefABCDEF"; for (String x : nums) {// Validate hexadecimal in range (0, 2**16):// 1. at least one and not more than 4 hexdigits in one chunkif (x.length() == 0 || x.length() > 4) return "Neither";// 2. only hexdigits are allowed: 0-9, a-f, A-Ffor (Character ch : x.toCharArray()) {if (hexdigits.indexOf(ch) == -1) return "Neither";} } return "IPv6"; } public String validIPAddress(String IP) {if (IP.chars().filter(ch -> ch == '.').count() == 3) {return validateIPv4(IP); } else if (IP.chars().filter(ch -> ch == ':').count() == 7) {return validateIPv6(IP); } else return "Neither"; }}
复杂度分析
时间复杂度：O(1)。
空间复杂度：O(1)。
BY /
本文作者：力扣
编辑&版式：霍霍
声明：本文归“力扣”版权所有，如需转载请联系。
点个在看，少个bug?
