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)
dfs虽然早就熟悉，但驾驭起来还是非常欠火候，而且碰到问题除非非的用dfs才会考虑，看了博主http://liaoxl.github.io/blog/20131124/leetcode-ripa/的文章，觉得dfs很强大，理解了思路，就自己实现下，仔细体会下dfs，还真的有那么点味道，这个题目不难，ip在0.0.0.0 - 255.255.255.255都是合法的，这里的程序就不做解释了，建议若看的不是很明白就自己copy到本机环境中，去单步下，很有意思，理解也更深刻，这个题本身就是一个题，但是dfs的思想还是蛮有趣。
class Solution {
public:
bool isValid(string sip){
if(sip.length() > 3 || sip.length() > 1 && sip[0] == ‘0‘) return false;
int sum = 0;
for(int i = 0; i < sip.length(); ++i){
sum *= 10;
sum += sip[i] - ‘0‘;
}
return (sum >= 0 && sum <= 255);
}
//ndot：ip地址四段三个“.",ndot表示已经处理的段数
//start：给定ip string 串的下标
void dfs(string s, int ndot, int start,string &cur_re, vector<string> &re){
if(ndot > 3 || start >= s.length()) return;
if(ndot == 3 && isValid(s.substr(start))){
cur_re.append(s.substr(start));
re.push_back(cur_re);
return;
}
for(int i = start; i < s.length() && i - start < 3; ++i){
// i - start < 3 : 4位以上可定就不合法了，不用继续了。
string sub = s.substr(start, i - start + 1);
if(isValid(sub)){
int len = cur_re.length();
cur_re.append(sub + ".");
dfs(s, ndot + 1, i + 1, cur_re, re);
cur_re.resize(len);
}
}
}
vector<string> restoreIpAddresses(string s) {
vector<string> re;
string cur_re;
//再少不能少于4个吧，再多也别多于12位
if(s.length() < 4 || s.length() > 12) return re;
dfs(s, 0, 0, cur_re, re);
return re;
}
};