题目描述
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
题解
DFS + 剪枝：每次取一个字符，要么直接拼上去，要么加个小数点再拼上去，然后剔除掉不符合条件的分支。
看评论区似乎要重点考虑“0”的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| vector<string> res;
void dfs(string &s, int start, int end,int count,string des)
{
if (count>end - start || 3 * count < end- start)return;
if (count == 0) {
string k = des.substr(1,des.length()-1);
int i = start;
while (i < end)
{
k = k + s[i];
i++;
}
res.push_back(k);
return;
}
int k = 0;
dfs(s, start + 1, end, count - 1,des+ '.' + s[start]);
if (s[start] != '0')
dfs(s, start + 2, end, count - 1, des + '.' + s[start] + s[start + 1] );
if(s[start] != '0'&&end-start>=3&&(s[start]-'0')*100+(s[start+1]-'0')*10+(s[start+2]-'0')<256)
dfs(s, start + 3, end, count - 1, des + '.' + s[start]+ s[start + 1] + s[start + 2] );
}
vector<string> restoreIpAddresses(string s) {
dfs(s, 0, s.length(), 4,"");
return res;
}
|
666，我自己都没想到这么快。
执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗 :8.4 MB, 在所有 C++ 提交中击败了89.69%的用户
字符串与数值的转化，已经有现成的函数，sscanf和sprintf要学会用了。
函数形参声明为引用，能提高效率。
回溯算法事实上就是在一个树形问题上做深度优先遍历。