【回溯】复原IP地址

解题思路：回溯算法

递归结束条件：字符串中的segment的数量为4，且startIndex为字符长度

1.创建一个大小为4的int数组，存放被分割的四个数

2.若递归条件满足，将path放入ans数组中。之后不论startIndex是否为字符长度，都返回：

a.创建一个临时的String数组，大小为字符长度+4

b.将每个数字重新变为字符

3.若第一个数字为0，直接进入下一层

4.若字符串在没被分成4个segment时就用完，直接返回

5.for循环，i从startIndex开始，到数组长度结束：

a.将从startIndex到i的数字字符变为数字，放入int数组中，同时'.'的数量+1

b.若数字大于0，小于255(0xFF)使用回溯算法

c.删除int数组中的数字，同时segment的数量-1

#define SEG_COUNT 4
int fourNums[SEG_COUNT];
int pathTop;
char** ans;
int ansTop;
void backTracking(char* s, int startIndex, int segNum) {
    if(segNum == SEG_COUNT) {
        if(startIndex == strlen(s)) {
            char* tempString = (char*)malloc(sizeof(char) * strlen(s) + 4);
            int add = 0;
            int j;
            for(j = 0; j < SEG_COUNT; j++) {
                int num = fourNums[j];
                if(num >= 100)
                    tempString[add++] = num / 100 + '0';
                if(num >= 10)
                    tempString[add++] = num % 100 / 10 + '0';
                tempString[add++] = num % 10 + '0';
                if(j != SEG_COUNT - 1)
                    tempString[add++] = '.';
            }
            tempString[add] = 0;
            ans = realloc(ans, sizeof(char*) * (ansTop + 1));
            ans[ansTop++] = tempString;
        }
        return;
    }
    if(startIndex == strlen(s))
        return;

    if(s[startIndex] == '0') {
        fourNums[segNum] = 0;
        backTracking(s, startIndex + 1, segNum + 1);
    }
    int i;
    int num = 0;
    for(i = startIndex; i < strlen(s); i++) {
        num = num * 10 +(s[i] - '0');
        if(num > 0 && num <= 0xFF) {
            fourNums[segNum] = num;
            backTracking(s, i + 1, segNum + 1);
        } else {
            break;
        }
        
    }
}

char ** restoreIpAddresses(char * s, int* returnSize){
    ans = (char**)malloc(0);
    ansTop = pathTop = 0;
    backTracking(s, 0, 0);
    *returnSize = ansTop;
    return ans;
}

另一种解法：用'.'的数量记录

//记录结果
char** result;
int resultTop;
//记录应该加入'.'的位置
int segments[3];
int isValid(char* s, int start, int end) {
    if(start > end)
        return 0;
    if (s[start] == '0' && start != end) { // 0开头的数字不合法
                return false;
    }
    int num = 0;
    for (int i = start; i <= end; i++) {
        if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
            return false;
        }
        num = num * 10 + (s[i] - '0');
        if (num > 255) { // 如果大于255了不合法
            return false;
        }
    }
    return true;
}

//startIndex为起始搜索位置，pointNum为'.'对象
void backTracking(char* s, int startIndex, int pointNum) {
    //若'.'数量为3，分隔结束
    if(pointNum == 3) {
        //若最后一段字符串符合要求，将当前的字符串放入result种
        if(isValid(s, startIndex, strlen(s) - 1)) {
            char* tempString = (char*)malloc(sizeof(char) * strlen(s) + 4);
            int j;
            //记录添加字符时tempString的下标
            int count = 0;
            //记录添加字符时'.'的使用数量
            int count1 = 0;
            for(j = 0; j < strlen(s); j++) {
                tempString[count++] = s[j];
                //若'.'的使用数量小于3且当前下标等于'.'下标，添加'.'到数组
                if(count1 < 3 && j == segments[count1]) {
                    tempString[count++] = '.';
                    count1++;
                }
            }
            tempString[count] = 0;
            //扩容result数组
            result = (char**)realloc(result, sizeof(char*) * (resultTop + 1));
            result[resultTop++] = tempString;
        }
        return ;
    }

    int i;
    for(i = startIndex; i < strlen(s); i++) {
        if(isValid(s, startIndex, i)) {
            //记录应该添加'.'的位置
            segments[pointNum] = i;
            backTracking(s, i + 1, pointNum + 1);
        }
        else {
            break;
        }
    }
}

char ** restoreIpAddresses(char * s, int* returnSize){
    result = (char**)malloc(0);
    resultTop = 0;
    backTracking(s, 0, 0);
    *returnSize = resultTop;
    return result;
}