LeetCode 791 自定义字符串排序

思路一

根据字符串S构建映射表，映射表用一个长度为26的数组表示。下标为i的内容表示字符'a' + i在S中出现的位置。比如S = "cba"，则映射表如下所示。

g_orderMap[0] = 2;
g_orderMap[1] = 1;
g_orderMap[2] = 0;
...

随后将字符串T中所有在S中出现的字符移动到T的前面，不在S中出现的字符移动到T的后面。比如T = "defgabc"，则移动后为T = "abcgfed"。注意这只是其中一种移动方法，题目对不在S中出现的字符的相对顺序没有做要求。所以T中所有不在S中出现的字符的顺序可以不用理会。

最后调用qsort对T的前半部分按照S给定的顺序排序即可。

static int g_orderMap[26];

static void BuildOrderMap(const char *s)
{
    int index = 0;

    memset(g_orderMap, -1, sizeof(int) * 26);
    while (*s != '') {
        g_orderMap[*s - 'a'] = index;
        ++index;
        ++s;
    }
}

// 将在order串中出现的字符移到字符串前；未出现的移到字符串后
static void DivideStr(char *result, int *endPos)
{
    int len = strlen(result);
    int left = 0;
    int right = len - 1;
    char *temp = NULL;
    int tempLen = sizeof(char) * len;

    temp = (char *)malloc(tempLen + 1);
    if (temp == NULL) { return; }
    memset(temp, 0, tempLen + 1);

    for (int i = 0; i < len; ++i) {
        if (g_orderMap[result[i] - 'a'] > -1) {
            temp[left++] = result[i];
        } else {
            temp[right--] = result[i];
        }
    }
    *endPos = left;
    memcpy(result, temp, tempLen + 1);

    free(temp);
}

static int cmp(const void *a, const void *b)
{
    const char *pa = (char *)a;
    const char *pb = (char *)b;
    int idxA = (int)(*pa - 'a');
    int idxB = (int)(*pb - 'a');

    return g_orderMap[idxA] - g_orderMap[idxB];
}

char *customSortString(char *s, char *t){
    char *result = NULL;
    int len = strlen(t);
    int endPos = 0;

    result = (char *)malloc(len + 1);
    if (result == NULL) { return NULL; }
    memset(result, 0, len + 1);
    memcpy(result, t, len);

    BuildOrderMap(s);
    DivideStr(result, &endPos);
    qsort(result, endPos, sizeof(char), cmp);

    return result;
}

思路二

看了一下题解，发现题解的思路更加巧妙。先统计T串中各个字符出现的次数，然后遍历S串，根据S串中字符的顺序逐个添加字符到结果字符串中。

char *customSortString(char *S, char *T)
{
    int idx = 0;
    int count[26];
    int len = strlen(T);
    char *result = NULL;

    result = (char *)malloc(len + 1);
    if (result == NULL) { return NULL; }
    memset(result, 0, len + 1);

    memset(count, 0, sizeof(int) * 26);
    for (int i = 0; i < len; ++i) {
        count[T[i] - 'a']++;
    }

    while (*S != '') {
        while (count[*S - 'a'] > 0) {
            result[idx++] = *S;
            count[*S - 'a']--;
        }
        S++;
    }
    
    // 将不在S串中出现的字符添加到result的末尾
    for (int i = 0; i < 26; ++i) {
        while (count[i] > 0) {
            result[idx++] = (char)('a' + i);
            count[i]--;
        }
    }

    return result;
}