现规定两种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"; } };