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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | 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) —
Last Post: How to Perform Case-insensitive Valid Palindrome AlphaNum String Check?
Next Post: C Sharp Extension Method