文章目录
题目
标题和出处
标题：验证IP地址
出处：468. 验证IP地址
难度
4 级
题目描述
要求
给你一个字符串 queryIP \texttt{queryIP} queryIP，如果是有效的 IPv4 地址则返回 "IPv4" \texttt{"IPv4"} "IPv4"，如果是有效的 IPv6 地址则返回 "IPv6" \texttt{"IPv6"} "IPv6"，如果不是上述类型的 IP 地址则返回 "Neither" \texttt{"Neither"} "Neither"。
有效的 IPv4 地址是形式为 "x 1 .x 2 .x 3 .x 4 " \texttt{"x}_\texttt{1}\texttt{.x}_\texttt{2}\texttt{.x}_\texttt{3}\texttt{.x}_\texttt{4}\texttt{"} "x1.x2.x3.x4" 的 IP 地址，其中 0 ≤ x i ≤ 255 \texttt{0} \le \texttt{x}_\texttt{i} \le \texttt{255} 0≤xi≤255 且 x i \texttt{x}_\texttt{i} xi 不能包含前导零。例如， "192.168.1.1" \texttt{"192.168.1.1"} "192.168.1.1" 和 "192.168.1.0" \texttt{"192.168.1.0"} "192.168.1.0" 是有效的 IPv4 地址， "192.168.01.1" \texttt{"192.168.01.1"} "192.168.01.1"、 "192.168.1.00" \texttt{"192.168.1.00"} "192.168.1.00" 和 "192.168@1.1" \texttt{"192.168@1.1"} "192.168@1.1" 是无效的 IPv4 地址。
有效的 IPv6 地址是形式为 "x 1 :x 2 :x 3 :x 4 :x 5 :x 6 :x 7 :x 8 " \texttt{"x}_\texttt{1}\texttt{:x}_\texttt{2}\texttt{:x}_\texttt{3}\texttt{:x}_\texttt{4}\texttt{:x}_\texttt{5}\texttt{:x}_\texttt{6}\texttt{:x}_\texttt{7}\texttt{:x}_\texttt{8}\texttt{"} "x1:x2:x3:x4:x5:x6:x7:x8" 的 IP 地址，其中：
- 1 ≤ x i .length ≤ 4 \texttt{1} \le \texttt{x}_\texttt{i}\texttt{.length} \le \texttt{4} 1≤xi.length≤4；
- x i \texttt{x}_\texttt{i} xi 是十六进制串，包含数字、小写字母（ ‘a’ \texttt{`a'} ‘a’ 到 ‘f’ \texttt{`f'} ‘f’）和大写字母（ ‘A’ \texttt{`A'} ‘A’ 到 ‘F’ \texttt{`F'} ‘F’）；
- 允许 x i \texttt{x}_\texttt{i} xi 包含前导零。
例如， "2001:0db8:85a3:0000:0000:8a2e:0370:7334" \texttt{"2001:0db8:85a3:0000:0000:8a2e:0370:7334"} "2001:0db8:85a3:0000:0000:8a2e:0370:7334" 和 "2001:db8:85a3:0:0:8A2E:0370:7334" \texttt{"2001:db8:85a3:0:0:8A2E:0370:7334"} "2001:db8:85a3:0:0:8A2E:0370:7334" 是有效的 IPv6 地址， "2001:0db8:85a3::8A2E:037j:7334" \texttt{"2001:0db8:85a3::8A2E:037j:7334"} "2001:0db8:85a3::8A2E:037j:7334" 和 "02001:0db8:85a3:0000:0000:8a2e:0370:7334" \texttt{"02001:0db8:85a3:0000:0000:8a2e:0370:7334"} "02001:0db8:85a3:0000:0000:8a2e:0370:7334" 是无效的 IPv6 地址。
示例
示例 1：
输入：
queryIP
=
"172.16.254.1"
\texttt{queryIP = "172.16.254.1"}
queryIP = "172.16.254.1"
输出：
"IPv4"
\texttt{"IPv4"}
"IPv4"
解释：有效的 IPv4 地址，返回
"IPv4"
\texttt{"IPv4"}
"IPv4"。
示例 2：
输入：
queryIP
=
"2001:0db8:85a3:0:0:8A2E:0370:7334"
\texttt{queryIP = "2001:0db8:85a3:0:0:8A2E:0370:7334"}
queryIP = "2001:0db8:85a3:0:0:8A2E:0370:7334"
输出：
"IPv6"
\texttt{"IPv6"}
"IPv6"
解释：有效的 IPv6 地址，返回
"IPv6"
\texttt{"IPv6"}
"IPv6"。
示例 3：
输入：
queryIP
=
"256.256.256.256"
\texttt{queryIP = "256.256.256.256"}
queryIP = "256.256.256.256"
输出：
"Neither"
\texttt{"Neither"}
"Neither"
解释：既不是 IPv4 地址，又不是 IPv6 地址。
示例 4：
输入：
queryIP
=
"2001:0db8:85a3:0:0:8A2E:0370:7334:"
\texttt{queryIP = "2001:0db8:85a3:0:0:8A2E:0370:7334:"}
queryIP = "2001:0db8:85a3:0:0:8A2E:0370:7334:"
输出：
"Neither"
\texttt{"Neither"}
"Neither"
示例 5：
输入：
queryIP
=
"1e1.4.5.6"
\texttt{queryIP = "1e1.4.5.6"}
queryIP = "1e1.4.5.6"
输出：
"Neither"
\texttt{"Neither"}
"Neither"
数据范围
- queryIP \texttt{queryIP} queryIP 仅由英语字母、数字、字符 ‘.’ \texttt{`.'} ‘.’ 和 ‘:’ \texttt{`:'} ‘:’ 组成
前言
有效的 IP 地址有两种，分别是 IPv4 地址和 IPv6 地址。任何一个有效的 IP 地址一定是其中的一种，因此我们可以依次判断给定的 IP 地址是否为有效的 IPv4 地址和 IPv6 地址。
由此可以得到如下代码框架：
class Solution {
public String validIPAddress(String queryIP) {
if (isValidIPv4(queryIP)) {
return "IPv4";
} else if (isValidIPv6(queryIP)) {
return "IPv6";
} else {
return "Neither";
}
}
}
判断给定的 IP 地址是否为有效的 IPv4 地址和 IPv6 地址有多种方法，可以将 IP 地址转成字符串数组然后判断，也可以直接遍历 IP 地址进行判断。
解法一
思路和算法
可以将 IP 地址转成字符串数组然后判断。以下分别说明 IPv4 地址和 IPv6 地址的判断方法。
对于 IPv4 地址的判断方法如下：
-
长度为 0 0 0 的 IP 地址不是 IPv4 地址；
-
如果 IP 地址以 ‘.’ \text{`.'} ‘.’ 开始或结束，则不是 IPv4 地址；
-
如果 IP 地址包含 ‘+’ \text{`+'} ‘+’ 或 ‘–’ \text{`--'} ‘–’，则不是 IPv4 地址，这一步判断是为了在第 7 步避免 ‘+’ \text{`+'} ‘+’ 和 ‘–’ \text{`--'} ‘–’ 对判断造成影响；
-
将给定的 IP 地址使用 ‘.’ \text{`.'} ‘.’ 作为分隔转成字符串数组；
-
如果字符串数组的长度不为 4 4 4，则不是 IPv4 地址；
-
判断字符串数组的每个元素，长度必须在 1 1 1 到 3 3 3 之间，且长度大于 1 1 1 时第一个字符不能为 0 0 0，如果不符合要求，则不是 IPv4 地址；
-
字符串数组的每个元素都应该可以转换成不超过 255 255 255 的整数，如果转换成的整数大于 255 255 255 或者转换失败（包含非数字的字符），则不是 IPv4 地址，可以通过 try-catch \texttt{try-catch} try-catch 块实现。
对于 IPv6 地址的判断方法如下：
-
长度为 0 0 0 的 IP 地址不是 IPv6 地址；
-
如果 IP 地址以 ‘:’ \text{`:'} ‘:’ 开始或结束，则不是 IPv6 地址；
-
将给定的 IP 地址使用 ‘:’ \text{`:'} ‘:’ 作为分隔转成字符串数组；
-
如果字符串数组的长度不为 8 8 8，则不是 IPv6 地址；
-
判断字符串数组的每个元素，长度必须在 1 1 1 到 4 4 4 之间，否则不是 IPv6 地址；
-
字符串数组的每个元素都只能包含十六进制表示的字符，包括数字、大写字母 ‘A’ \text{`A'} ‘A’ 到 ‘F’ \text{`F'} ‘F’ 和小写字母 ‘a’ \text{`a'} ‘a’ 到 ‘f’ \text{`f'} ‘f’，否则不是 IPv6 地址。
代码
class Solution {
public String validIPAddress(String queryIP) {
if (isValidIPv4(queryIP)) {
return "IPv4";
} else if (isValidIPv6(queryIP)) {
return "IPv6";
} else {
return "Neither";
}
}
public boolean isValidIPv4(String queryIP) {
int queryIPLength = queryIP.length();
if (queryIPLength == 0) {
return false;
}
if (queryIP.charAt(0) == '.' || queryIP.charAt(queryIPLength - 1) == '.') {
return false;
}
if (queryIP.indexOf('+') >= 0 || queryIP.indexOf('-') >= 0) {
return false;
}
String[] array = queryIP.split("\\.");
if (array.length != 4) {
return false;
}
int length = array.length;
for (int i = 0; i < length; i++) {
String numStr = array[i];
if (numStr.length() == 0 || numStr.length() > 3 || numStr.length() > 1 && numStr.charAt(0) == '0') {
return false;
}
try {
int num = Integer.parseInt(numStr);
if (num > 255) {
return false;
}
} catch (NumberFormatException ex) {
return false;
}
}
return true;
}
public boolean isValidIPv6(String queryIP) {
int queryIPLength = queryIP.length();
if (queryIPLength == 0) {
return false;
}
if (queryIP.charAt(0) == ':' || queryIP.charAt(queryIPLength - 1) == ':') {
return false;
}
String[] array = queryIP.split(":");
if (array.length != 8) {
return false;
}
int length = array.length;
for (int i = 0; i < length; i++) {
String numStr = array[i];
if (numStr.length() == 0 || numStr.length() > 4) {
return false;
}
int curLength = numStr.length();
for (int j = 0; j < curLength; j++) {
char c = numStr.charAt(j);
if (!isHexChar(c)) {
return false;
}
}
}
return true;
}
private boolean isHexChar(char c) {
return Character.isDigit(c) || Character.isUpperCase(c) && c <= 'F' || Character.isLowerCase(c) && c <= 'f';
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是字符串 queryIP \textit{queryIP} queryIP 的长度。判断 IPv4 地址最多需要遍历字符串数组两次，判断 IPv6 地址最多需要遍历字符串数组一次，每次遍历字符串数组需要 O ( n ) O(n) O(n) 的时间。
-
空间复杂度： O ( n ) O(n) O(n)，其中 n n n 是字符串 queryIP \textit{queryIP} queryIP 的长度。需要将字符串 queryIP \textit{queryIP} queryIP 转成字符串数组，数组中的各元素长度之和不超过 n n n。
解法二
思路和算法
也可以直接遍历 IP 地址进行判断。在遍历的过程中，维护 IP 地址的片段数，判断每个片段的字符是否合法。
以下分别说明 IPv4 地址和 IPv6 地址的判断方法。
对于 IPv4 地址的判断如下：
-
片段之间使用 ‘.’ \text{`.'} ‘.’ 分隔；
-
每个片段只包含数字，且每个片段的数字不超过 255 255 255；
-
当一个片段的长度大于 1 1 1 时，不能有前导零；
-
不能有两个相邻的 ‘.’ \text{`.'} ‘.’；
-
共有 4 4 4 个片段。
对于 IPv6 地址的判断方法如下：
-
片段之间使用 ‘:’ \text{`:'} ‘:’ 分隔；
-
每个片段的长度必须在 1 1 1 到 4 4 4 之间；
-
每个片段只能包含十六进制表示的字符，包括数字、大写字母 ‘A’ \text{`A'} ‘A’ 到 ‘F’ \text{`F'} ‘F’ 和小写字母 ‘a’ \text{`a'} ‘a’ 到 ‘f’ \text{`f'} ‘f’；
-
不能有两个相邻的 ‘:’ \text{`:'} ‘:’；
-
共有 8 8 8 个片段。
具体实现方面，遍历 IP 地址时，如果遇到不合法的字符则直接返回 false \text{false} false，对于合法字符，遇到非分隔符和分隔符时（分隔符指 IPv4 的 ‘.’ \text{`.'} ‘.’ 和 IPv6 的 ‘:’ \text{`:'} ‘:’），分别进行如下操作：
-
遇到非分隔符时，更新当前片段的状态并判断当前片段是否符合要求；
-
遇到分隔符时，如果发现相邻两个字符都是分隔符则直接返回 false \text{false} false，其余情况则将片段数量加 1 1 1。
遍历结束时需要再次对片段数量加 1 1 1，然后对片段数量和最后一个片段进行判断。
代码
class Solution {
public String validIPAddress(String queryIP) {
if (isValidIPv4(queryIP)) {
return "IPv4";
} else if (isValidIPv6(queryIP)) {
return "IPv6";
} else {
return "Neither";
}
}
public boolean isValidIPv4(String queryIP) {
int num = 0;
int count = 0;
char prev = '.';
int length = queryIP.length();
for (int i = 0; i < length; i++) {
char curr = queryIP.charAt(i);
if (Character.isDigit(curr)) {
if (num == 0 && prev == '0') {
return false;
}
num = num * 10 + curr - '0';
if (num > 255) {
return false;
}
} else if (curr == '.') {
if (prev == '.') {
return false;
}
count++;
num = 0;
} else {
return false;
}
prev = curr;
}
count++;
return num <= 255 && count == 4 && prev != '.';
}
public boolean isValidIPv6(String queryIP) {
int count = 0;
int partLength = 0;
char prev = ':';
int length = queryIP.length();
for (int i = 0; i < length; i++) {
char curr = queryIP.charAt(i);
if (isHexChar(curr)) {
partLength++;
if (partLength > 4) {
return false;
}
} else if (curr == ':') {
if (prev == ':') {
return false;
}
count++;
partLength = 0;
} else {
return false;
}
prev = curr;
}
count++;
return count == 8 && prev != ':';
}
private boolean isHexChar(char c) {
return Character.isDigit(c) || Character.isUpperCase(c) && c <= 'F' || Character.isLowerCase(c) && c <= 'f';
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是字符串 queryIP \textit{queryIP} queryIP 的长度。需要遍历字符串 queryIP \textit{queryIP} queryIP 一次。
-
空间复杂度： O ( 1 ) O(1) O(1)。