Restore IP Addresses
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given "25525511135"
,
return ["255.255.11.135", "255.255.111.35"]
. (Order does not matter)
思路:
一共有三个点要确定位置,每一个IP字段的长度是1到3之间的一个数字。穷举的话也无非是最多27种可能性。
题解:
class Solution { public: vector<string> validated; void verify(const string& s, size_t* l) { string ip; size_t accumu = 0; for(size_t i = 0; i < 4; ++i) { // cut the digit string strval = s.substr(accumu, l[i]); accumu += l[i]; // validate the starting zero problem if (strval.size() > 1 && strval[0] == '0') return; // validate the digit int val = atoi(strval.c_str()); if (val <= 255) { ip += strval; if (i != 3) ip += '.'; } else return; } validated.push_back(ip); } vector<string> restoreIpAddresses(string s) { size_t input_len = s.size(); validated.clear(); size_t lens[4]; for(lens[0] = 1; lens[0] <= 3; ++lens[0]) for(lens[1] = 1; lens[1] <= 3; ++lens[1]) for(lens[2] = 1; lens[2] <= 3; ++lens[2]) if (lens[0] + lens[1] + lens[2] >= input_len) break; else { lens[3] = input_len - lens[0] - lens[1] - lens[2]; verify(s, lens); } return validated; } };