题目：

Given a string containing only digits, restore it by returning all possible valid IP address combinations. （Medium）

For example:
Given "25525511135",

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

分析：

使用回溯法即可。helper函数用来处理DFS过程，isValid判断一个子串是否符合IP地址一个点分十进制的一块。

注意在isValid中要除去类似00，01这种0打头的情况。

代码：

class Solution {
private:
vector result;
bool isValid(const string& s) {
if (s[] == '' && s.size() > ) { // for case like "00.122.122.122"
return false;
}
int num = stoi(s);
if (num >= && num <= ) { return true; } return false; } void helper(const string& s, string curS, int start, int step) { if (step == ) { if (start != s.size()) { return; } curS.pop_back(); result.push_back(curS); return; } for (int i = ; i <= ; ++i) { if (start + i <= s.size()) { string tempS = s.substr(start, i); if (isValid(tempS)) { string newS = curS + tempS; newS.push_back('.'); helper(s, newS, start + i, step + ); } } } } public: vector restoreIpAddresses(string s) {
string curS;
helper(s, curS, , );
return result;
}
};