思路
回溯(backtracing)，用s的起始位置pos表示当前的状态（pos之前的已经处理完）。那么就依次尝试1~3位的字符看看是否符合要求，符合就把结果更新到buffer里，未完成就递归继续，然后递归返回的时候记得把buffer恢复到之前的状态。
按照题目的意思，应该不允许IP地址有前导0，即01.01.01.01这种状态.
对了，stoi函数很好用，应该是C++11新加的。
代码
class Solution {
public:
bool isValidSubAddr(const string& s, int pos, int len){
if(pos + len > s.size())
return false;
int val = stoi(s.substr(pos, len));
if(val >= 0 && val <= 255){
if(val < 10 && len > 1)
return false;
else if(val < 100 && len > 2)
return false;
return true;
}
return false;
}
void restoreSub(vector<string>& results, const string& s, int pos, int remainingDot, string& buffer){
if(remainingDot == 0 || pos >= s.size())
return;
int buffSize = buffer.size();
for(int len=1; len<=3; len++){
if(!isValidSubAddr(s, pos, len))
continue;
buffer += s.substr(pos, len);
if(pos + len == s.size()){
//one solution
if(remainingDot == 1) //otherwise, the split cannot be finished
results.push_back(buffer);
} else {
buffer += ".";
//continue try
restoreSub(results, s, pos+len, remainingDot-1, buffer);
}
buffer.erase(buffSize); //restore state
}
}
vector<string> restoreIpAddresses(string s) {
vector<string> results;
if(s.empty()){
return results;
}
string buffer;
restoreSub(results, s, 0, 4, buffer);
return results;
}
};