O(n) Algorithm, one For loop Do Anything!, not use any system function


  • 0
    S
    O(n) Algorithm, one For loop Do Anything!
    public string[] stateInfo = new string[3] { "IPv4", "IPv6", "Neither" };
            private static bool First = false;
            private static int []chMap;
    public string ValidIPAddress(string IP)
            {
    	    // not use if get Ascii Char
                if (First == false) {
                    First = true;
                    chMap = new int[256];
                    for (int i = 0; i < 256; ++i) {
                        chMap[i] = -1;
                        if (i >= '0' && i <= '9') {
                            chMap[i] = i - '0';
                        }
    
                        if (i >= 'a' && i <= 'f') {
                            chMap[i] = 10 + i - 'a';
                        }
    
                        if (i >= 'A' && i <= 'F') {
                            chMap[i] = 10 + i - 'A';
                        }
    
                        if (i == '.' || i == ':') {
                            chMap[i] = -2;
                        }
                    }
                }
    
    
                int type = 10, nowType = 0;
                int unitSize = 0;
                int semiCount = 0;
                // can be a public static property, so fast
                var save = new int[5] {0,0,0,0,0};
                int rs10 = 0;
                // append a split for algorithm complete
                IP += ":";
                foreach (var ch in IP) {
                    var val = chMap[ch];
    
                    // unavid char 
                    if(val == -1) {
                        goto NEITHER;
                    }
    
                    if (ch == '.' || ch == ':') {
                        semiCount++;
                        // deside ipv4 or ipv6 by first split char
                        if(nowType == 0) {
                            nowType = ch == '.' ? 10 : 16;
                        }
    
                        // is ipv4 but find "1e1."
                        if (type != nowType && type == 16) {
                            goto NEITHER;
                        }
    
                        // empty
                        if (unitSize == 0)
                            goto NEITHER;
    
                        // ipv4 every node smaller than 256
                        if (nowType == 10) {
                            if(unitSize > 3 || rs10 > 255)
                                goto NEITHER;
    
    
    			// '0' at head
                            if (unitSize > 1) {
                                if(save[0] == 0)
                                    goto NEITHER;
                            }
                        }
    
                        save[0] = 0;
                        save[1] = 0;
                        save[2] = 0;
                        save[3] = 0;
                        save[4] = 0;
                        unitSize = 0;
                        rs10 = 0;
                        continue;
                    }
    
                    // node is ipv6?
                    if (val >= 10)
                        type = 16;
    
                    save[unitSize] = val;
                    unitSize ++;
                    // calc ipv4 sum
    	        if(nowType != 16) {
                        rs10 *= 10;
                        rs10 += val;
                    }
                    if (unitSize > 4)
                        goto NEITHER;
                }
    
                if (semiCount != 4 && semiCount != 8)
                    goto NEITHER;
                if(nowType == 10) goto IPv4;
                if(nowType == 16) goto IPV6;
                if(nowType == 0) goto NEITHER;
    
            IPv4:
                return stateInfo[0];
    
            IPV6:
                return stateInfo[1];
    
            NEITHER:
                return stateInfo[2];
            }
    

Log in to reply
 

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