xiaoxiao2021-03-25  19

现规定两种IP地址，分别为IPV4和IPV6。IPV4由4个10进制数（0~255）组成，只允许有单独的0出现，数字之间用“.”分隔；

IPV6用8个16进制组成，每个数的长度最多不超过4，允许单独的0出现，数字之间用“：”分隔。

Input: "172.16.254.1" Output: "IPv4" Explanation: This is a valid IPv4 address, return "IPv4". Input: "2001:0db8:85a3:0:0:8A2E:0370:7334" Output: "IPv6" Explanation: This is a valid IPv6 address, return "IPv6".

部分思路：

1.首先确定开头不能为标点；

2.“.”则不能出现“：”；

3.IPV4有4个“.”；

4.IPV4不能出现字母

5.IPV4的数字长度小于4

自己想的思路时间复杂度太高，在discuss找的几个方法的时间复杂度也是太高。

class Solution { private: bool validIPv4(string &IP) { int begin = 0, end = 0, cnt = 0; while (end < IP.size()) { int leadingZeroCount = 0, num = 0; while (end < IP.size() && isdigit(IP[end])) { num = num * 10 + IP[end] - '0'; if (IP[end] == '0' && num == 0) leadingZeroCount++; if ((leadingZeroCount > 0 && num != 0) || leadingZeroCount > 1 || end - begin + 1 > 3 || num > 255) return false; ++end; } if (end == begin) return false; ++cnt; if (cnt <= 3) { if (end >= IP.size() || IP[end] != '.') return false; begin = ++end; } else { if (end != IP.size()) return false; } } return cnt == 4; } bool validIPv6(string &IP) { int cnt = 0, begin = 0, end = 0; while (end < IP.size()) { while (end < IP.size() && isalnum(IP[end])) { if ((IP[end] > 'f' && IP[end] <= 'z') || (IP[end] > 'F' && IP[end] <= 'Z') || end - begin + 1 > 4) return false; ++end; } if (begin == end) return false; ++cnt; if (cnt <= 7) { if (end >= IP.size() || IP[end] != ':') return false; begin = ++end; } else { if (end != IP.size()) return false; } } return cnt == 8; } public: string validIPAddress(string IP) { if (validIPv4(IP)) return "IPv4"; if (validIPv6(IP)) return "IPv6"; return "Neither"; } };