C++_O(n)_AC_One-Pass Solution


  • 0
    class Solution {
    public:
    string validIPAddress(string IP) {
        if(IP.empty() || IP.size() > 39) return "Neither";
        bool colon = false, dot = false, leadingZero = false, larger255 = false, letter = false;
        int colonCount = 0, dotCount = 0;
        int digitCount = 0;
        for(int i = 0; i < IP.size();){
            if(isdigit(IP[i])){
                int sum = 0;
                if(IP[i] == '0'){
                    if(i == 0) {return "Neither";}
                    if(dot && i + 1 < IP.size() && isdigit(IP[i+1])){return "Neither";}
                }//"192.0.0.1" || "192.0.0.0"
                while(isdigit(IP[i])){
                    if(leadingZero) return "Neither";
                    sum = sum*10 + (IP[i] - '0');
                    ++i;
                    digitCount++;
                    if(digitCount > 4) return "Neither";
                }
                if(sum > 255) larger255 = true;
                if(dot && larger255) return "Neither";
                leadingZero = false;
                larger255 = false;
            }else if(IP[i] == ':'){
                if(i-1>=0 && IP[i-1] == ':') return "Neither";
                colon = true;
                colonCount++;
                if(dot || colonCount > 7 || letter || digitCount > 4) return "Neither";
                digitCount = 0;
                ++i;
            }else if(IP[i] == '.'){
                if(i-1>=0 && IP[i-1] == '.') return "Neither";
                dot = true;
                dotCount++;
                if(colon || dotCount > 3 || larger255 || digitCount > 3) return "Neither";
                digitCount = 0;
                ++i;
            }else if((IP[i] - 'a' >= 0 && IP[i] - 'f' <= 0) || (IP[i] - 'A' >= 0 && IP[i] - 'F' <= 0)){
                letter = false;
                digitCount++;
                if(dot) return "Neither";
                ++i;
            }else{
                return "Neither";
            }
        }
        if((colon && (colonCount != 7 || digitCount > 4)) || (dot && (dotCount != 3 || digitCount > 3))) return "Neither";
        
        return colon ? "IPv6" : "IPv4";
    }
    };

  • 0

    Didn't check into details but a true one-pass solution!

    For loop "while(isdigit(IP[i]))", maybe add a bound check to avoid index out of bound plus possible early break, e.g., IP="123456789".

    Actually, index "i" doesn't have to go to IP.size() since any valid IP address has length at most 39.


  • 0

    @zzg_zzm Hiiii, so nice to see you again buddy! Yep, I have updated my code, thanks for your advise!!!!!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.