93. Restore IP Addresses
dfs，回溯+剪枝。。。就我觉得中等题做到后面，完成一道题花的时间越来越长吗？下面说下思路
- 用
left和right变量控制ip地址每段的范围，其中：left作为每段起始点，且在每次函数调用中向后递进，即dfs(ans, s, depth + 1, right + 1, temp + ts + ".");；righr作为每段终点，同时也是循环变量，调整每段的长度和大小；right作为当前段终点，如果剩下的ip段长度不符合要求（即剩下的每段长度必须在1-3之间），则舍弃；
temp变量记录到当前位置，已经转化好的ip字符串；depth表示当前是ip中第几段；
注意点和小技巧：
- 每段ip的要求不仅是0-255，同时每段不得有前置零，且不得删除任何一个数，即ip地址总长度不能变
- 字符串与数值的转化，虽然写起来不难，但已经有现成的函数可用。。。
sscanf和sprintf了解一下 - 函数形参声明为引用，能提高效率
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> ans;
dfs(ans, s, 1, 0, "");
return ans;
}
void dfs(vector<string> &ans, string &s, int depth, int left, string temp) {
if (left >= s.length()) return ;
for (int right = left; right < s.length() && right <= left + 2; right++) {
if (s.length() - right - 1 > 3 * (4 - depth)) continue;
if (s.length() - right - 1 < (4 - depth)) continue;
char ts[4];
int i = 0;
for (; i <= right - left; i++) ts[i] = s[i+left];
ts[i] = '\0';
if (is_ip(ts)) {
if (depth == 4) {
temp += ts;
ans.push_back(temp);
return ;
}
dfs(ans, s, depth + 1, right + 1, temp + ts + ".");
}
}
}
bool is_ip(const char ts[]) {
int a;
sscanf(ts, "%d", &a);
if (0 <= a && a < 256) return true;
else return false;
}
};
