Coding Exercise - Restore IP Addresses - C++ - Online Judge

Question: Given a string containing only numbers, restore it by returning all possible IP addresses (in a vector)

Original Problem Page: http://oj.leetcode.com/problems/restore-ip-addresses/

Examples:

Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

A valid IP address consists of four numbers ranging from 0 to 255 inclusive. Given a string length small than 4 or larger than 12, we can say it is impossible to construct a valid IP address using all numbers.

Please not, a leading zero is not allowed, so ‘00.2.3.33’ is not valid. (‘0.2.3.33’ is valid instead, that is, you can’t write extra leading zeros)

The problem scale is so small, so you can just bruteforce all possible combinations. We can separate the string into four numbers by putting three dots.

The first dot comes after 1, 2, 3, digit and no more. In each loop (we check the number and if it is invalid, we discard the current loop [continue] . After reaching the inner loop, we have four numbers and check the third and fourth number. If all valid, we push the result into the vector.

class Solution {
public:
    vector restoreIpAddresses(string s) {
        int n = s.length(); // get length
        vector ip;  // result put here
        // if length > 12 or < 4 mission impossible         
        if ((n > 12) || (n < 4)) return ip;
        // the first dot placed after [1, 3] digits
        for (int i = 1; i <= 3; i ++) {             
                string a = s.substr(0, i); // get first number             
                // can't lead with zero unless it is zero             
                if ((a[0] == '0') && (a.length() > 1)) continue;
                int aa = atoi(a.c_str());
                // bigger than 255 not valid
                if (aa > 255) continue;
                // second dot 
                for (int j = i + 1; j <= n - 2; j ++) {                 
                        string b = s.substr(i, j - i);                 
                        if ((b[0] == '0') && (b.length() > 1)) continue;
                        int bb = atoi(b.c_str());
                        if (bb > 255) continue;
                        // third dot
                        for (int k = j + 1; k <= n - 1; k ++) {                     
                                string c = s.substr(j, k - j);                     
                                if ((c[0] == '0') && (c.length() > 1)) continue;
                                int cc = atoi(c.c_str());
                                if (cc > 255) continue;
                                string d = s.substr(k, n - k);
                                if ((d[0] == '0') && (d.length() > 1)) continue;
                                int dd = atoi(d.c_str());
                                if (dd > 255) continue;
                                // ok four numbers are all valid, so it is valid IP
                                ip.push_back(to_string(aa) + "." + to_string(bb) + "." + 
                                                to_string(cc) + "." + to_string(dd));
                        }
                }
        }
        return ip;
    }
};

class Solution {
public:
    vector restoreIpAddresses(string s) {
        int n = s.length(); // get length
        vector ip;  // result put here
        // if length > 12 or < 4 mission impossible         
        if ((n > 12) || (n < 4)) return ip;
        // the first dot placed after [1, 3] digits
        for (int i = 1; i <= 3; i ++) {             
                string a = s.substr(0, i); // get first number             
                // can't lead with zero unless it is zero             
                if ((a[0] == '0') && (a.length() > 1)) continue;
                int aa = atoi(a.c_str());
                // bigger than 255 not valid
                if (aa > 255) continue;
                // second dot 
                for (int j = i + 1; j <= n - 2; j ++) {                 
                        string b = s.substr(i, j - i);                 
                        if ((b[0] == '0') && (b.length() > 1)) continue;
                        int bb = atoi(b.c_str());
                        if (bb > 255) continue;
                        // third dot
                        for (int k = j + 1; k <= n - 1; k ++) {                     
                                string c = s.substr(j, k - j);                     
                                if ((c[0] == '0') && (c.length() > 1)) continue;
                                int cc = atoi(c.c_str());
                                if (cc > 255) continue;
                                string d = s.substr(k, n - k);
                                if ((d[0] == '0') && (d.length() > 1)) continue;
                                int dd = atoi(d.c_str());
                                if (dd > 255) continue;
                                // ok four numbers are all valid, so it is valid IP
                                ip.push_back(to_string(aa) + "." + to_string(bb) + "." + 
                                                to_string(cc) + "." + to_string(dd));
                        }
                }
        }
        return ip;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...

487 words
Last Post: How to Perform Case-insensitive Valid Palindrome AlphaNum String Check?
Next Post: C Sharp Extension Method

The Permanent URL is: Coding Exercise – Restore IP Addresses – C++ – Online Judge