Simple & generic C++ solution - 9ms


  • 0
    A

    As it has been discussed previously, this problem has a straightforward solution nesting 3 loops. But what about IPv6 or MAC addresses? 5 nested loops? What if the number of bytes of the address is N? N-1 nested loops with template metaprogramming? If N is read from stdin, the loop-based approach is invalid. Just for learning, here I propose a clean and generic solution that works for any address of size N:

    class Solution {
        typedef vector<string> VS;
        typedef vector<int> VI;
        const int N_BYTES_ADDR = 4;
    public:
        VS restoreIpAddresses(string s) {
            VS sols;
            VI sol(N_BYTES_ADDR);
            ipAddrImpl(0, 0, s, sol, sols);
            return sols;
        }
    private:
        void ipAddrImpl(int byte, int offset, const string& s, VI& sol, VS& sols) {
            int n = s.size(); 
            if (byte == N_BYTES_ADDR) {
    			if (offset == n) sols.push_back(toString(sol));
    		}
            else {
                for (int digits = 1; digits <= min(3, n-offset); ++digits) {
                    sol[byte] = num(s, offset, digits);
                    // Continue if its int representation can be fit in a byte
                    // and has the expected number of digits and (avoids errors
                    // when multiple zeroes are together: 0.00.0.0 is NOT an IPv4 address)
                    if (countDigits(sol[byte]) == digits && sol[byte] <= 255) 
                        ipAddrImpl(byte+1, offset+digits, s, sol, sols);
                }
            }
        }
        int countDigits(int n) {
            int count = 1;
            while (n > 9) {
                ++count;
                n /= 10;
            }
    		return count;
        }
        int num(const string& s, int offset, int digits) { 
            int acc = 0;
            if (digits == 3) acc += (s[offset]-'0')*100;
            if (digits >= 2) acc += (s[offset+digits-2]-'0')*10;
            if (digits >= 1) acc += s[offset+digits-1]-'0';
            return acc;
        };
        string toString(const VI& sol) {
            string res = to_string(sol[0]);
            for (int i = 1; i < N_BYTES_ADDR; ++i) res = res + "." + to_string(sol[i]);
            return res;
        }
    };

  • -1
    M

    Thanks for sharing.

    However I don't think countDigits is necessary here.

    If the number of digits doesn't match, then this must be the leading zero. You only need to make sure it either is zero or doesn't have any leading zeros.

    Thus, this will save you tiny bit time.

    (sol[byte] == 0 || s[offset] != '0') //countDigits(sol[byte]) == digits

  • 0
    A

    Thanks for your comment but if you do it this way you are not checking that the code is not "omitting" real zeroes in the string:

    Input: "010010"

    Output: ["0.1.0.10","0.10.0.10","0.100.1.0"]

    Expected: ["0.10.0.10","0.100.1.0"]


Log in to reply
 

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