# 复原 IP 地址
给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000"
输出：["0.0.0.0"]
示例 3：
输入：s = "1111"
输出：["1.1.1.1"]
示例 4：
输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]
示例 5：
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
0 <= s.length <= 3000s 仅由数字组成
以下程序实现了这一功能，请你填补空白处内容：
```cpp
#include
#include
#include
#include
static bool valid(char *ip, int len)
{
if (len > 1 && ip[0] == '0')
{
return false;
}
if (len == 3)
{
int n = (ip[0] - '0') * 100 + (ip[1] - '0') * 10 + (ip[2] - '0');
if (n > 255)
{
return false;
}
}
return true;
}
#define WIDTH 4
static void dfs(char *s, int start, char *stack, int num, char **results, int *count)
{
int i, j;
if (num == 4)
{
if (s[start] == '\0')
{
results[*count] = malloc(3 * 4 + 3 + 1);
char *p = results[*count];
for (j = 0; j < num; j++)
{
char *q = stack + j * WIDTH;
______________________;
}
(*count)++;
}
}
else
{
char *p = stack + num * WIDTH;
char *q = p;
for (i = start; s[i] != '\0' && i < start + 3; i++)
{
*q++ = s[i];
*q = '\0';
if (!valid(p, q - p))
{
return;
}
dfs(s, i + 1, stack, num + 1, results, count);
if (num + 1 < 4)
{
memset(stack + (num + 1) * WIDTH, 0, WIDTH);
}
}
}
}
static char **restoreIpAddresses(char *s, int *returnSize)
{
int count = 0;
char **results = malloc(100 * sizeof(char *));
char addr[16] = {'\0'};
dfs(s, 0, addr, 0, results, &count);
*returnSize = count;
return results;
}
int main(int argc, char **argv)
{
if (argc != 2)
{
fprintf(stderr, "Usage: ./test num\n");
exit(-1);
}
int i, count = 0;
char **list = restoreIpAddresses(argv[1], &count);
for (i = 0; i < count; i++)
{
printf("%s\n", list[i]);
}
}
```
## template
```cpp
#include
#include
#include
#include
static bool valid(char *ip, int len)
{
if (len > 1 && ip[0] == '0')
{
return false;
}
if (len == 3)
{
int n = (ip[0] - '0') * 100 + (ip[1] - '0') * 10 + (ip[2] - '0');
if (n > 255)
{
return false;
}
}
return true;
}
#define WIDTH 4
static void dfs(char *s, int start, char *stack, int num, char **results, int *count)
{
int i, j;
if (num == 4)
{
if (s[start] == '\0')
{
results[*count] = malloc(3 * 4 + 3 + 1);
char *p = results[*count];
for (j = 0; j < num; j++)
{
char *q = stack + j * WIDTH;
while ((*p++ = *q++) != '\0')
{
}
if (j != 3)
{
*(p - 1) = '.';
}
}
(*count)++;
}
}
else
{
char *p = stack + num * WIDTH;
char *q = p;
for (i = start; s[i] != '\0' && i < start + 3; i++)
{
*q++ = s[i];
*q = '\0';
if (!valid(p, q - p))
{
return;
}
dfs(s, i + 1, stack, num + 1, results, count);
if (num + 1 < 4)
{
memset(stack + (num + 1) * WIDTH, 0, WIDTH);
}
}
}
}
static char **restoreIpAddresses(char *s, int *returnSize)
{
int count = 0;
char **results = malloc(100 * sizeof(char *));
char addr[16] = {'\0'};
dfs(s, 0, addr, 0, results, &count);
*returnSize = count;
return results;
}
int main(int argc, char **argv)
{
if (argc != 2)
{
fprintf(stderr, "Usage: ./test num\n");
exit(-1);
}
int i, count = 0;
char **list = restoreIpAddresses(argv[1], &count);
for (i = 0; i < count; i++)
{
printf("%s\n", list[i]);
}
}
```
## 答案
```cpp
while ((*p++ = *q++) != '\0')
{
}
if (j != 3)
{
*(p - 1) = '.';
}
```
## 选项
### A
```cpp
while ((*p++ = *q++) != '\0')
{
*p++;
}
if (j != 3)
{
*(p - 1) = '.';
}
```
### B
```cpp
while ((*p++ = *q++) != '\0')
{
*p++;
}
if (j != 3)
{
*p = '.';
}
```
### C
```cpp
while ((*p++ = *q++) != '\0')
{
}
if (j != 3)
{
*p = '.';
}
```