833. 字符串中的查找与替换[leetcode]

对于某些字符串 S，我们将执行一些替换操作，用新的字母组替换原有的字母组（不一定大小相同）。

每个替换操作具有 3 个参数：起始索引 i，源字 x 和目标字 y。规则是如果 x 从原始字符串 S 中的位置 i 开始，那么我们将用 y 替换出现的 x。如果没有，我们什么都不做。

举个例子，如果我们有 S = “abcd” 并且我们有一些替换操作 i = 2，x = “cd”，y = “ffff”，那么因为 “cd” 从原始字符串 S 中的位置 2 开始，我们将用 “ffff” 替换它。

再来看 S = “abcd” 上的另一个例子，如果我们有替换操作 i = 0，x = “ab”，y = “eee”，以及另一个替换操作 i = 2，x = “ec”，y = “ffff”，那么第二个操作将不执行任何操作，因为原始字符串中 S[2] = 'c'，与 x[0] = 'e' 不匹配。

所有这些操作同时发生。保证在替换时不会有任何重叠： S = "abc", indexes = [0, 1], sources = ["ab","bc"] 不是有效的测试用例。

示例 1：

输入：S = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
输出："eeebffff"
解释：
"a" 从 S 中的索引 0 开始，所以它被替换为 "eee"。
"cd" 从 S 中的索引 2 开始，所以它被替换为 "ffff"。
示例 2：

输入：S = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
输出："eeecd"
解释：
"ab" 从 S 中的索引 0 开始，所以它被替换为 "eee"。
"ec" 没有从原始的 S 中的索引 2 开始，所以它没有被替换。

提示：

0 <= indexes.length = sources.length = targets.length <= 100
0 < indexes[i] < S.length <= 1000
给定输入中的所有字符都是小写字母。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-and-replace-in-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

执行用时 :8 ms, 在所有 C 提交中击败了43.48%的用户
内存消耗 :7.5 MB, 在所有 C 提交中击败了74.24%的用户

void exchange(int *nums,int idx,int idx2){
    int tmp = nums[idx];
    nums[idx] = nums[idx2];
    nums[idx2] = tmp;
}

int *sort(int *index,int size){
    int *result = calloc(sizeof(int), size);
    int *tmp = calloc(sizeof(int), size);
    if (!result || !tmp) {
        return NULL;
    }
    for (int i=0; i<size; i++) {
        result[i] = i;
        tmp[i] = index[i];
    }

    for (int i=0; i<size; i++) {
        bool change = false;
        for (int j=0; j<size-1-i; j++) {
            if (tmp[j] < tmp[j+1]) {
                exchange(tmp, j, j+1);
                exchange(result, j, j+1);
                change = true;
            }
        }
        if (!change) {
            break;
        }
    }
//    printAll(tmp, size);
    if (tmp) {
        free(tmp);
    }
    return result;
}

char * findReplaceString(char * S, int* indexes, int indexesSize, char ** sources, int sourcesSize, char ** targets, int targetsSize){

    unsigned long mallocLen = strlen(S);
    unsigned long originLen = mallocLen;
    int *myOrder = sort(indexes, indexesSize);
    if (!myOrder) {
        return NULL;
    }
//    printAll(myOrder, indexesSize);

//    int *sourcesLens = calloc(sizeof(int), sourcesSize);
//    int *targetsLens = calloc(sizeof(int), sourcesSize);
//    if (!sourcesLens || !targetsLens ) {
//        return NULL;
//    }
    for (int i=0; i<indexesSize; i++) {
        int sIndex = indexes[i];
        char *sourceStr = sources[i];
        unsigned long sourceStrLen = strlen(sourceStr);
        if(memcmp(S+sIndex, sourceStr , sourceStrLen) !=0 ){
            indexes[i] = -1;
        }else{
//            sourcesLens[i] = (int)sourceStrLen;
            int targetStrLen = (int)strlen(targets[i]);
            mallocLen += targetStrLen - sourceStrLen;
        }
    }

    char *result = calloc(sizeof(char), mallocLen+1);
    if (!result) {
        return NULL;
    }
    int pos = mallocLen-1;
    int lastIndex = originLen;
    for (int k=0; k<indexesSize; k++) {
        int i = myOrder[k];
        int sIndex = indexes[i];
        if (sIndex<0) {
            continue;
        }
        char *sourceStr = sources[i];
        unsigned long sourceStrLen = strlen(sourceStr);


            //剩余串长度 lastIndex - sIndex - sourceStrLen;
        //最后剩余串起始位置. sIndex + sourceStrLen

        // 将后面地串搬下来.
        unsigned long end = pos+1-(lastIndex - sIndex - sourceStrLen);
        for (unsigned long start = pos; pos>=end ; pos--) {
            result[pos] = S[lastIndex-1 -(start-pos)];
//            printf("%zd-%c\n",pos,result[pos]);
        }
//        printf("%s\n", result+pos+1);

        // 将替换地字符串拼进来.
        char *targetStr = targets[i];
        unsigned long targetStrLen = strlen(targetStr);
        for (int j=0; j<targetStrLen; j++) {
            result[pos--] = targetStr[targetStrLen-1-j];
        }
//        printf("%s\n", result+pos+1);
        lastIndex = sIndex;
    }

    for (; pos>=0 ; pos--) {
        result[pos] = S[pos];
//        printf("%d-%c\n",pos,result[pos]);
    }
//    printf("%s\n", result+pos+1);
    if (myOrder) {
        free(myOrder);
    }

    return result;
}