Leetcode 468. Validate IP Address
Problem Explanation
The goal of this problem is to determine whether a given input string represents a valid IPv4 or IPv6 address.
For a string to be considered a valid IPv4 address, it needs to meet the following criteria:
- It has to consist of four numbers separated by periods (e.g. 10.0.0.1).
- Each of these numbers is within the range 0-255 inclusive.
- No leading zeroes are allowed in the numbers.
For a string to be a valid IPv6 address, it should satisfy these rules:
- It has to comprise eight groups of hexadecimal numbers (digits 0-9 and letters A-F, either in upper or lower case), separated by colons (e.g. 2001:0db8:85a3:0:0:8A2E:0370:7334).
- Each group contains 1 to 4 characters.
- No leading zeroes are allowed in the groups.
A string that doesn't meet either of these sets of rules is considered 'Neither'.
Let's take an example to illustrate:
Example 1: Input: "172.16.254.1" Output: "IPv4"
In this example, the input string is a valid IPv4 address since it meets all the criteria. It is made up of four numbers, each between 0 and 255, separated by periods, and none of the numbers have leading zeroes.
Solution Approach
The provided solution uses the 'istringstream' in C++ to split the input string into parts. This is quite similar to using 'split' method in other languages.
For IPv4 validation, the solution counts the number of periods in the string. If it is 3, the string can possibly be a valid IPV4 address. For each part of the string separated by a period, it checks whether it's a valid part of an IPV4 address. If one part is not valid, it returns "Neither".
For IPv6, it counts the number of colons in the string. If it is 7, the solution considers that the string could be a valid IPV6 address. It does similar checks on each part of the string separated by a colon as IPv4.
Any string that does not pass either of the two checks is assumed to be "Neither".
Python Solution
1 2python 3class Solution: 4 def validIPAddress(self, IP): 5 blocks = IP.split('.') 6 if len(blocks) == 4: 7 for i in range(4): 8 if not blocks[i].isdigit() or not 0 <= int(blocks[i]) < 256 or \ 9 (blocks[i][0] == '0' and len(blocks[i]) > 1): 10 return "Neither" 11 return "IPv4" 12 13 blocks = IP.split(':') 14 if len(blocks) == 8: 15 for i in range(8): 16 if not (1 <= len(blocks[i]) <= 4) or \ 17 not all(c in string.hexdigits for c in blocks[i]): 18 return "Neither" 19 return "IPv6" 20 21 return "Neither"
Java Solution
1
2java
3public class Solution {
4 public String validIPAddress(String IP) {
5 String[] ipv4 = IP.split("\\.",-1);
6 String[] ipv6 = IP.split("\\:",-1);
7 if(IP.chars().filter(ch -> ch == '.').count() == 3){
8 for(String s : ipv4) if(isIPv4(s)) continue;else return "Neither";
9 return "IPv4";
10 }
11 if(IP.chars().filter(ch -> ch == ':').count() == 7){
12 for(String s : ipv6) if(isIPv6(s)) continue;else return "Neither";
13 return "IPv6";
14 }
15 return "Neither";
16 }
17 public boolean isIPv4(String s){
18 try{ return String.valueOf(Integer.valueOf(s)).equals(s) && Integer.parseInt(s) >= 0 && Integer.parseInt(s) <= 255;}
19 catch (NumberFormatException e){return false;}
20 }
21 public boolean isIPv6(String s){
22 if (s.length()> 4) return false;
23 try {return Integer.parseInt(s, 16) >= 0 && s.charAt(0) != '-';}
24 catch (NumberFormatException e){return false;}
25 }
26}
Javascript Solution
1
2javascript
3var validIPAddress = function(IP) {
4 let ipv4 = IP.split(".");
5 let ipv6 = IP.split(":");
6 if(ipv4.length==4){
7 for(let i of ipv4){
8 if(i=="" || i.length>1 && i[0]=="0" || !/^[0-9]+$/.test(i) || Number(i)>255){
9 return "Neither";
10 }
11 }
12 return "IPv4";
13 }
14 if(ipv6.length==8){
15 for(let i of ipv6){
16 if(i=="" || i.length>4 || !/^[0-9a-fA-F]+$/.test(i)){
17 return "Neither";
18 }
19 }
20 return "IPv6";
21 }
22 return "Neither";
23};
C++ Solution
1
2cpp
3class Solution {
4public:
5 string validIPAddress(string IP) {
6 stringstream ss(IP);
7 string block;
8 // ipv4 candidate
9 if (IP.find('.') != string::npos) {
10 for (int i = 0; i < 4; i++) {
11 if (!getline(ss, block, '.') || !isValidIPv4Block(block))
12 return "Neither";
13 }
14 return ss.eof() ? "IPv4" : "Neither";
15 }
16 // ipv6 candidate
17 else if (IP.find(':') != string::npos) {
18 for (int i = 0; i < 8; i++) {
19 if (!getline(ss, block, ':') || !isValidIPv6Block(block))
20 return "Neither";
21 }
22 return ss.eof() ? "IPv6" : "Neither";
23 }
24 return "Neither";
25 }
26
27private:
28 const string validIPv6Chars = "0123456789abcdefABCDEF";
29
30 bool isValidIPv4Block(string& block) {
31 int num = 0;
32 if (block.size() > 0 && block.size() <= 3) {
33 for (int i = 0; i < block.size(); i++) {
34 char c = block[i];
35 // invalid character
36 if (!isalnum(c) || (i == 0 && c == '0' && block.size() > 1))
37 return false;
38 else {
39 num *= 10;
40 num += c - '0';
41 }
42 }
43 return num <= 255;
44 }
45 return false;
46 }
47
48 bool isValidIPv6Block(string& block) {
49 if (block.size() > 0 && block.size() <= 4) {
50 for (int i = 0; i < block.size(); i++) {
51 char c = block[i];
52 if (validIPv6Chars.find(c) == string::npos)
53 return false;
54 }
55 return true;
56 }
57 return false;
58 }
59};
C# Solution
1
2csharp
3public class Solution {
4 public string ValidIPAddress(string IP) {
5 if (ValidateIPv4(IP)) return "IPv4";
6 if (ValidateIPv6(IP)) return "IPv6";
7 return "Neither";
8 }
9
10 public bool ValidateIPv4(string IP) {
11 var arr = IP.Split(".");
12 if (arr.Length != 4) return false;
13 foreach (var str in arr) {
14 if (str.Length == 0 || str.Length > 3) return false;
15 for (int i = 0; i < str.Length; i++) if (!Char.IsDigit(str[i])) return false;
16 if (str.Length >= 2 && str[0] == '0') return false;
17 if (int.Parse(str) > 255) return false;
18 }
19 return true;
20 }
21
22 public bool ValidateIPv6(string IP) {
23 var arr = IP.Split(":");
24 if (arr.Length != 8) return false;
25 foreach (var str in arr) {
26 if (str.Length == 0 || str.Length > 4) return false;
27 for (int i = 0; i < str.Length; i++) if (!Char.IsDigit(str[i]) &&
28 (str[i] < 'a' || str[i] > 'f') &&
29 (str[i] < 'A' || str[i] > 'F')) return false;
30 }
31 return true;
32 }
33}
Each solution traverses each digit of each string part to validate it in the function isValidIPv4Block (for IPv4), and isValidIPv6Block (for IPv6). This can be seen especially well in the C++ solution. Other programming languages perform equivalent checks.
Note for JavaScript: It uses regex to validate each part of the string. i==""
checks if the part is not empty, i.length>1 && i[0]=="0"
makes sure there are no leading zeroes, !/^[0-9]+$/.test(i)
checks if it is a digit, and Number(i)>255
ensures it's less than or equal to 255. For IPv6, i==""
checks if the part is not empty, i.length>4
makes sure it's not more than 4 characters, and !/^[0-9a-fA-F]+$/.test(i)
checks if it's a valid digit or a letter between a-f either lower or upper case.
Ruby solution
1 2ruby 3class Solution 4 def valid_i_p_address(i_p) 5 blocks = i_p.split('.') 6 if blocks.length == 4 7 for i in 0..3 8 return 'Neither' unless blocks[i].match(/\A[01]?\d\d?(?!.)|(?!0\d)\d\d?(?!.)|(?!0{2,}\d)2[0-4]\d(?!.)|(?!0{2,})25[0-5](?!.)\z/) 9 end 10 return 'IPv4' 11 end 12 13 blocks = i_p.split(':') 14 if blocks.length == 8 15 for i in 0..7 16 return 'Neither' unless blocks[i].match(/\A[\da-fA-F]{1,4}\z/) 17 end 18 return 'IPv6' 19 end 20 21 'Neither' 22 end 23end
In this Ruby solution, we use regular expressions to determine if the IPv4 and IPv6 addresses are valid. The regular expression for IPv4 addresses checks if the number is between 0 and 255 and it does not allow leading zeroes. For IPv6 addresses, the regular expression checks that each section contains between 1 and 4 hexadecimal digits.
R solution
1 2r 3validIPAddress=function(IP){ 4 blocks = strsplit(IP, ".")[[1]] 5 if (length(blocks) == 4) { 6 for (i in 1:4) { 7 if (!grepl("^[0-9]+$",blocks[i]) || as.integer(blocks[i])<0 || as.integer(blocks[i])>255 || nchar(blocks[i])!=nchar(trimws(blocks[i], "l"))){ 8 return("Neither") 9 } 10 } 11 return("IPv4") 12 } 13 14 blocks = strsplit(IP, ":")[[1]] 15 if (length(blocks)==8){ 16 for (i in 1:8){ 17 if (nchar(blocks[i])>4 || !grepl("^[0-9a-fA-F]+$",blocks[i])){ 18 return("Neither") 19 } 20 } 21 return("IPv6") 22 } 23 return("Neither") 24}
In the R solution, we use the grepl
function with appropriate regular expressions to check if each part of the address is a digit in the case of IPv4, or a hexadecimal digit in the case of IPv6. Note that for IPv4, we also check that each number is between 0 and 255, and that there are no leading zeroes.
In all the solutions, the function splits the input into sections, each of which must satisfy the relevant criteria for the address type. If all parts pass these checks, the function identifies the input as the corresponding IP version. If any part fails, or if the input does not split into the expected number of parts, the function returns 'Neither'.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.