Restore IP AddressesAug 8 '12
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given
Given
"25525511135"
,
return
["255.255.11.135", "255.255.111.35"]
. (Order does not matter)DFS
class Solution { public: vector<string> restoreIpAddresses(string s) { // Start typing your C/C++ solution below // DO NOT write int main() function if (s.size() > 12 || s.size() < 4) return vector<string>(); return getValidIP(s.c_str(), 0); } vector<string> getValidIP(const char *c, int n) { const char *head = c; if (n == 3) { int num = 0; while (*c != '\0') { num = num * 10 + *c - '0'; ++c; } vector<string> ret; // last segment requirements // at least one digit and at most one leading zero if (c - head > 1 && *head == '0' || c == head) return ret; // segment number cannot exceed 255 if (num <= 255) { string seg(head, c - head); ret.push_back(seg); } return ret; } int num = 0; vector<string> ret; for (int i = 0; i < 3; ++i) { // reaches end or digits exceed 3 if (*c == '\0' || c - head > 2) break; num = num * 10 + *c - '0'; // each segment can be at most 255 if (num > 255) break; vector<string> rest = getValidIP(++c, n + 1); string add_seg(head, c - head); for (auto s : rest) { string address(add_seg); address += "."; address += s; ret.push_back(address); } // only one leading 0 allowed if (*(c - 1) == '0' && i == 0) break; } return ret; } };
No comments:
Post a Comment