Massive Algorithms: LeetCode 468 - Validate IP Address

LeetCode 468 - Validate IP Address

https://leetcode.com/problems/validate-ip-address/

In this problem, your job to write a function to check whether a input string is a valid IPv4 address or IPv6 address or neither.

IPv4 addresses are canonically represented in dot-decimal notation, which consists of four decimal numbers, each ranging from 0 to 255, separated by dots ("."), e.g.,172.16.254.1;

Besides, you need to keep in mind that leading zeros in the IPv4 is illegal. For example, the address 172.16.254.01 is illegal.

IPv6 addresses are represented as eight groups of four hexadecimal digits, each group representing 16 bits. The groups are separated by colons (":"). For example, the address 2001:0db8:85a3:0000:0000:8a2e:0370:7334 is a legal one. Also, we could omit some leading zeros among four hexadecimal digits and some low-case characters in the address to upper-case ones, so 2001:db8:85a3:0:0:8A2E:0370:7334 is also a valid IPv6 address(Omit leading zeros and using upper cases).

However, we don't replace a consecutive group of zero value with a single empty group using two consecutive colons (::) to pursue simplicity. For example, 2001:0db8:85a3::8A2E:0370:7334 is an invalid IPv6 address.

Besides, you need to keep in mind that extra leading zeros in the IPv6 is also illegal. For example, the address 02001:0db8:85a3:0000:0000:8a2e:0370:7334 is also illegal.

Note: You could assume there is no extra space in the test cases and there may some special characters in the input string.

Example 1:

Input: "172.16.254.1"

Output: "IPv4"

Explanation: This is a valid IPv4 address, return "IPv4".

Example 2:

Input: "2001:0db8:85a3:0:0:8A2E:0370:7334"

Output: "IPv6"

Explanation: This is a valid IPv6 address, return "IPv6".

Example 3:

Input: "256.256.256.256"

Output: "Neither"

Explanation: This is neither a IPv4 address nor a IPv6 address.

http://bookshadow.com/weblog/2016/12/11/leetcode-validate-ip-address/
字符串模拟题，根据规则逐一验证即可
http://www.cnblogs.com/grandyang/p/6185339.html

LeetCode之前有一道关于IPv4的题Restore IP Addresses，给我们了一个字符串，让我们通过在中间加点来找出所有正确的IP地址，这道题给了我们中间加点或者冒号的字符串，让我们验证其是否是正确的IPv4或者IPv6，感觉要稍稍复杂一些。那么我们只有分别来验证了，那么我们怎么样能快速的区别是IPv4或者IPv6呢，当然是通过中间的点或者冒号啦，所以我们首先在字符串中找冒号(当然你想找点也可以)，如果字符串中没有冒号，那么我们来验证其是否是IPv4，如果有冒号，我们就来验证其是否是IPv6.

首先对于IPv4，我们使用getline函数来截取两个点之间的字符串，我们还需要一个计数器cnt来记录我们已经截取了多少段，如果cnt大于4了，说明超过了4段，说明是不是正确的地址。如果取出的字符串为空，说明两个点连在一起了，也不对。再有就是如果字符串长度大于1，且第一个字符是0，也不对。由于IPv4的地址在0到255之间，所以如果字符串长度大于3，也不正确。下面我们检查每一个字符，如果有不是数字的字符，返回Neither。最后我们再把字符串转为数字，如果不在0到255之间就是非法的。最后的最后，我们要保证cnt正好为4，而且最后一个字符不能是点，统统满足以上条件才是正确的IPv4地址。

然后对于IPv6，我们也使用getline函数来截取两个冒号之间的字符串，我们同样需要计数器cnt来记录我们已经截取了多少段，如果cnt大于8了，说明超过了8段，说明是不是正确的地址。如果取出的字符串为空，说明两个冒号连在一起了，也不对。面我们检查每一个字符，正确的字符应该是0到9之间的数字，或者a到f，或A到F之间的字符，如果出现了其他字符，返回Neither。最后的最后，我们要保证cnt正好为8，而且最后一个字符不能是冒号，统统满足以上条件才是正确的IPv6地址

    string validIPAddress(string IP) {
        istringstream is(IP);
        string t = "";
        int cnt = 0;
        if (IP.find(':') == string::npos) { // Check IPv4
            while (getline(is, t, '.')) {
                ++cnt;
                if (cnt > 4 || t.empty() || (t.size() > 1 && t[0] == '0') || t.size() > 3) return "Neither";
                for (char c : t) {
                    if (c < '0' || c > '9') return "Neither";
                }
                int val = stoi(t);
                if (val < 0 || val > 255) return "Neither";
            }
            return (cnt == 4 && IP.back() != '.') ? "IPv4" : "Neither";
        } else { // Check IPv6
            while (getline(is, t, ':')) {
                ++cnt;
                if (cnt > 8 || t.empty() || t.size() > 4) return "Neither";
                for (char c : t) {
                    if (!(c >= '0' && c <= '9') && !(c >= 'a' && c <= 'f') && !(c >= 'A' && c <= 'F')) return "Neither";
                }
            }
            return (cnt == 8 && IP.back() != ':') ? "IPv6" : "Neither";
        }
    }

https://leetcode.com/problems/validate-ip-address/discuss/95491/java-simple-solution

public String validIPAddress(String IP) {
 if(isValidIPv4(IP)) return "IPv4";
 else if(isValidIPv6(IP)) return "IPv6";
 else return "Neither";
}

public boolean isValidIPv4(String ip) {
 if(ip.length()<7) return false;
 if(ip.charAt(0)=='.') return false;
 if(ip.charAt(ip.length()-1)=='.') return false;
 String[] tokens = ip.split("\\.");
 if(tokens.length!=4) return false;
 for(String token:tokens) {
  if(!isValidIPv4Token(token)) return false;
 }
 return true;
}
public boolean isValidIPv4Token(String token) {
 if(token.startsWith("0") && token.length()>1) return false;
 try {
  int parsedInt = Integer.parseInt(token);
  if(parsedInt<0 || parsedInt>255) return false;
  if(parsedInt==0 && token.charAt(0)!='0') return false;
 } catch(NumberFormatException nfe) {
  return false;
 }
 return true;
}
 
public boolean isValidIPv6(String ip) {
 if(ip.length()<15) return false;
 if(ip.charAt(0)==':') return false;
 if(ip.charAt(ip.length()-1)==':') return false;
 String[] tokens = ip.split(":");
 if(tokens.length!=8) return false;
 for(String token: tokens) {
  if(!isValidIPv6Token(token)) return false;
 }
 return true;
}
public boolean isValidIPv6Token(String token) {
 if(token.length()>4 || token.length()==0) return false;
 char[] chars = token.toCharArray();
 for(char c:chars) {
  boolean isDigit = c>=48 && c<=57;
  boolean isUppercaseAF = c>=65 && c<=70;
  boolean isLowerCaseAF = c>=97 && c<=102;
  if(!(isDigit || isUppercaseAF || isLowerCaseAF)) 
   return false;
 }
 return true;
}

http://www.cnblogs.com/EdwardLiu/p/6213521.html

 2     public String validIPAddress(String IP) {
 3         if (IP==null || IP.length()==0) return "Neither";
 4         boolean isIP4 = checkIP4(IP);
 5         boolean isIP6 = checkIP6(IP);
 6         if (isIP4) return "IPv4";
 7         if (isIP6) return "IPv6";
 8         return "Neither";
 9     }
10     
11     public boolean checkIP4(String IP) {
12         if (IP.charAt(IP.length()-1) == '.') return false;
13         String[] numbers = IP.split("\\.");
14         if (numbers==null || numbers.length!=4) return false;
15         for (String str : numbers) {
16             if (str.length()==0 || str.length()>3) return false;
17             if (str.length()>1 && str.charAt(0)=='0') return false;
18             int val = 0;
19             for (int i=0; i<str.length(); i++) {
20                 char c = str.charAt(i);
21                 if (c<'0' || c>'9') return false;
22                 val = val*10 + (int)(c-'0');
23             }
24             if (val<0 || val>255) return false;
25         }
26         return true;
27     }
28     
29     public boolean checkIP6(String IP) {
30         if (IP.charAt(IP.length()-1) == ':') return false;
31         String[] numbers = IP.split(":");
32         if (numbers==null || numbers.length!=8) return false;
33         for (String str : numbers) {
34             if (str.length()==0 || str.length()>4) return false;
35             int i = 0;
36             while (i < str.length()) {
37                 char c = str.charAt(i++);
38                 if ((c<'0' || c>'9') && (c<'a' || c>'f') && (c<'A' || c>'F')) return false;
39             }
40         }
41         return true;
42     }

X. Regex
https://leetcode.com/problems/validate-ip-address/discuss/95504/Java-Simple-Solution-with-RegExp

    public String validIPAddress(String IP) {
        if(IP.matches("(([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])\\.){3}([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])"))return "IPv4";
        if(IP.matches("(([0-9a-fA-F]{1,4}):){7}([0-9a-fA-F]{1,4})"))return "IPv6";
        return "Neither";
    }

LeetCode 468 - Validate IP Address

Labels

Popular Posts