【LeetCode】 468. Validate IP Address

Description

Write a function to check whether an 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, leading zeros in the IPv4 is invalid. For example, the address 172.16.254.01 is invalid.

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 valid 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, extra leading zeros in the IPv6 is also invalid. For example, the address 02001:0db8:85a3:0000:0000:8a2e:0370:7334 is invalid.

Note: You may assume there is no extra space or special characters in the input string.

寫一個程式去判斷輸入字串是否為合法的IPv4位址、IPv6位址還是兩者皆否。

IPv4位址的規範是dot-decimal，其中包含四個0到255的十進位數字並使用小數點來分開。例如：172.16.254.1。

另外，前導零在IPv4中是不合法的。例如172.16.254.01這個位址是不合法的。

IPv6用八組四個16進位的字(每組代表16 bits)表示。每組之間使用冒號(":")分開。例如，2001:0db8:85a3:0000:0000:8a2e:0370:7334是合法的位址。我們可以省略四個16進制的數字中的前導零，也可以將小寫字母改為大寫，因此2001:db8:85a3:0:0:8A2E:0370:7334也是一個合法IPv6的位址(省略前導零和使用大寫字母)。

然而，為求簡單，我們不允許使用兩個冒號取代連續值為零的組別，例如2001:0db8:85a3::8A2E:0370:7334是不合法的IPv6位址。

此外，在IPv6中多餘的前導零是不合法的。例如：02001:0db8:85a3:0000:0000:8a2e:0370:7334是不合法的位址。

提示: 你可以假設輸入字串中沒有多餘的空白或是特別字元。

Example:

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.

Solution

• 這一題雖說難度只有Medium，但麻煩程度絕對是Hard。
• 因為需要處理大量的錯誤輸入，會需要蠻多不同的funciton，
  • 有時候想不到有哪些錯誤輸入要處理的時候，可以先submit看看，再針對測資去修改。
• 我們先想想演算法流程：
  1. 辨識IPv4還是IPv6(使用. :辨識)
  2. 將數字組取出
  3. 如果是IPv4：
     1. 確認組數
     2. 確認空組
     3. 檢查前導零
     4. 檢查是否為十進位字母(isdigit)
     5. 檢查數字大小合法(0~255)
  4. 如果是IPv6：
     1. 確認組數
     2. 確認空組
     3. 檢查多餘的前導零(直接檢查組裡面的字數就好)
     4. 檢查是否為十六進位字母(isxdigit)
     5. 檢查數字大小合法(0~65535)
  • 如果submit後發現有錯誤再另外針對錯誤去稍微修改。
• 接下來對於流程中的步驟分別實作即可。
• 如果全部手刻可能有點累，不妨查看看有沒有內建的function或lib可以幫助我們完成功能。
  • isdigit、isxdigit協助檢查數字
  • stringstream協助hex轉換
  • substr協助我們分割字串

---

• 下方code比較難的部分是myIsdigit()裡面使用了function pointer，如果不懂可以自行查詢相關資料或是直接分成兩個function完成。

Code

class Solution {
public:
    bool leaderZero(string num)
    {
        for(int i = 0; i < num.length(); i++)
        {
            if(num[i] == '0' && i != num.length() - 1)
                return true;
        }
        return false;
    }
    
    bool myIsdigit(string num, int (*op)(int))
    {
        for(int i = 0; i < num.length(); i++)
        {
            if(op(num[i]) == 0)
                return true;
        }
        return false;
    }
    
    string validIPAddress(string IP) {
        char delimiter;
        vector<string> nums;
        
        if(IP.length() > 40)
            return "Neither";
        
        /* check IP type */
        if(find(IP.begin(), IP.end(), '.') != IP.end())
            delimiter = '.';
        else
            delimiter = ':';
        
        /* split numbers */
        size_t pos = 0;
        string token;
        while ((pos = IP.find(delimiter)) != string::npos) {
            token = IP.substr(0, pos);
            nums.push_back(token);
            IP.erase(0, pos + 1);
        }
        nums.push_back(IP);
        
        /* IPV4 */
        if(delimiter == '.')
        {
            if(nums.size() != 4)
                return "Neither";
            for(int i = 0; i < nums.size(); i++)
            {
                if(nums[i].empty()) return "Neither";
                if(leaderZero(nums[i])) return "Neither";
                if(myIsdigit(nums[i], &isdigit)) return "Neither";
                int temp = stoi(nums[i]);
                if(temp > 255 || temp < 0) return "Neither";
            }
            return "IPv4";
        }
        /* IPV6 */
        else
        {
            if(nums.size() != 8)
                return "Neither";
            stringstream ss;
            int temp;
            for(int i = 0; i < nums.size(); i++)
            {
                if(nums[i].empty()) return "Neither";
                if(nums[i].length() > 4) return "Neither";
                if(myIsdigit(nums[i], &isxdigit)) return "Neither";
                ss << std::hex << nums[i];
                ss >> temp;
                ss.clear();
                if(temp > 65535 || temp < 0) return "Neither";
            }
            return "IPv6";
        }
    }
};

tags: LeetCode C++