找到字符串中所有字母异位词(Find All Anagrams in a String)

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。

示例 1:

输入:
s: "cbaebabacd" p: "abc"

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

示例 2:

输入:
s: "abab" p: "ab"

输出:
[0, 1, 2]

解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findAnagrams(char * s, char * p, int* returnSize){
    // 要初始化为NULL
    int* result = NULL;
    int resultLen = 0;
    
    int lenS = strlen(s);
    int lenP = strlen(p);
    int countP['z'-'a'+1] = {0};
    for (int i = 0; i < lenP; ++i) {
        countP[p[i]-'a']++;
    }
    for (int i = 0; i < lenS-lenP+1; ++i) {
        int countS['z'-'a'+1] = {0};
        for (int j = 0; j < lenP; ++j) {
            countS[s[i+j]-'a']++;
        }
        bool isSame = true;
        for (char c = 'a'; c <= 'z' ; c++) {
            if (countS[c-'a'] != countP[c-'a']) {
                isSame = false;
                break;
            }
        }
        if (isSame){
            resultLen++;
            result = realloc(result, (resultLen+1)*sizeof(int));
            result[resultLen-1] = i;
        }
    }
    *returnSize = resultLen;
    return result;
}

这个是比较直接的做法，时间复杂度为 O(n^2)

int* findAnagrams(char * s, char * p, int* returnSize){
    int* result = NULL;
    int resultLen = 0;
    
    int lenS = strlen(s);
    int lenP = strlen(p);
    if (lenS < lenP) {
        *returnSize = resultLen;
        return result;
    }
    int countP['z'-'a'+1] = {0};
    for (int i = 0; i < lenP; ++i) {
        countP[p[i]-'a']++;
    }
    int countS['z'-'a'+1] = {0};
    for (int i = 0; i < lenP; ++i) {
        countS[s[i]-'a']++;
    }
    int diffCount = 0;
    for (char c = 'a' ; c <= 'z'; c++) {
        if (countS[c-'a'] != countP[c-'a']){
            diffCount++;
        }
    }
    for (int i = 0; i < lenS; ++i) {
        if (diffCount == 0) {
            resultLen++;
            result = realloc(result, resultLen * sizeof(int));
            result[resultLen - 1] = i;
        }

        countS[s[i] - 'a']--;
        if (countS[s[i] - 'a'] + 1 == countP[s[i] - 'a']
        && countS[s[i] - 'a'] != countP[s[i] - 'a']) {
            diffCount++;
        }
        if (countS[s[i] - 'a'] + 1 != countP[s[i] - 'a']
        && countS[s[i] - 'a'] == countP[s[i] - 'a']) {
            diffCount--;
        }

        if (i + lenP < lenS) {
            countS[s[i + lenP] - 'a']++;
            if (countS[s[i+lenP] - 'a'] - 1 == countP[s[i+lenP] - 'a']
                && countS[s[i+lenP] - 'a']      != countP[s[i+lenP] - 'a']) {
                diffCount++;
            }
            if (countS[s[i+lenP] - 'a'] - 1 != countP[s[i+lenP] - 'a']
                && countS[s[i+lenP] - 'a']      == countP[s[i+lenP] - 'a']) {
                diffCount--;
            }
        }

    }
    *returnSize = resultLen;
    return result;
}

经过巧妙地改进，时间复杂度由O(n^2) 变成了 O(n) 真不错，这个有点类似与滑动窗口了

我们也可以只用一个数组，去存储他们的相差


int* findAnagrams(char * s, char * p, int* returnSize){
    int* result = NULL;
    int resultLen = 0;

    int lenS = strlen(s);
    int lenP = strlen(p);
    if (lenS < lenP) {
        *returnSize = resultLen;
        return result;
    }
    int countDiff['z'-'a'+1] = {0};
    for (int i = 0; i < lenP; ++i) {
        countDiff[p[i]-'a']++;
    }
    for (int i = 0; i < lenP; ++i) {
        countDiff[s[i]-'a']--;
    }
    int diffCount = 0;
    for (char c = 'a' ; c <= 'z'; c++) {
        if (countDiff[c-'a'] != 0){
            diffCount++;
        }
    }
    for (int i = 0; i < lenS; ++i) {
        if (diffCount == 0) {
            resultLen++;
            result = realloc(result, resultLen * sizeof(int));
            result[resultLen - 1] = i;
        }

        countDiff[s[i] - 'a']++;
        if (countDiff[s[i] - 'a'] - 1 == 0
        && countDiff[s[i] - 'a'] != 0) {
            diffCount++;
        }
        if (countDiff[s[i] - 'a'] - 1 != 0
        && countDiff[s[i] - 'a'] == 0) {
            diffCount--;
        }

        if (i + lenP < lenS) {
            countDiff[s[i + lenP] - 'a']--;
            if (countDiff[s[i+lenP] - 'a'] + 1 == 0
                && countDiff[s[i+lenP] - 'a']  != 0) {
                diffCount++;
            }
            if (countDiff[s[i+lenP] - 'a'] + 1 != 0
                && countDiff[s[i+lenP] - 'a']  == 0) {
                diffCount--;
            }
        }

    }
    *returnSize = resultLen;
    return result;
}