[C++知识库]C语言----复原 IP 地址

?此题用dfs回溯

#define NUM_MAX 100

void backtrack(char *s, int s_len, int step, char **p, int *returnSize, char **a)
{
    int i = 0;        // 用于选择列表扩展，字符从选1个至3个
    char temp[4];     // 用于临时存储选择后的字符串
    int num = 0;      // 用于将选择后的字符串转化为int类型做合法判断
    char *s_position; // 做选择和取消选择时，备份恢复s

    // 如果选择4次，并且字符被使用完，则满足结束条件
    if (step == 4) 
    {
        if ((strlen(a[0]) + strlen(a[1]) + strlen(a[2]) + strlen(a[3])) == s_len) 
        {
            // 分配内存
            p[*returnSize] = (char *)malloc(16 * sizeof(char));
            if (p[*returnSize] == NULL) 
            {
                return;
            }
            memset(p[*returnSize], 0, 16 * sizeof(char));
            // 格式化结果
            snprintf(p[*returnSize],16, "%s.%s.%s.%s", a[0], a[1], a[2], a[3]);
            (*returnSize)++;
            return;
        }
        return;
        
    }

    memset(temp, 0, 4 * sizeof(char));
    // 选择列表扩展
    for (i = 1; i <= 3; i++) {
        // 如果剩余选择的字符个数不够扩展，返回
        if (strlen(s) < i) {
            return;
        }
        memcpy(temp, s, i * sizeof(char));
        num = atoi(temp);
        // 判断选择后的字符是否合法（超过255，或者含有前导0）
        if (num > 255 || (s[0] == '0' && i!=1)) 
        {
            return;
        }
        // 做选择
        memcpy(a[step], s, i * sizeof(char));
        s_position = s; // 备份s
        backtrack(s+i, s_len, step + 1, p, returnSize, a);
        // 取消选择
        memset(a[step], 0, 4 * sizeof(char));
        s = s_position; // 恢复s
    }

    return;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char **restoreIpAddresses(char *s, int *returnSize)
{
    char **p = (char **)malloc(NUM_MAX * sizeof(char *));
    if (p == NULL) {
        return NULL;
    }

    // a用于临时存储符合条件的ip
    char **a = (char **)malloc(4 * sizeof(char *));
    if (a == NULL) 
    {
        return NULL;
    }
    for (int i = 0; i < 4; i++) 
    {
        a[i] = (char *)malloc(4 * sizeof(char));
        if (a[i] == NULL) {
            return NULL;
        }
        memset(a[i], 0, 4 * sizeof(char));
    }
    
    *returnSize = 0;
    backtrack(s, strlen(s), 0, p, returnSize, a);
    return p;
}

?

?