LeetCode 438. Find All Anagrams

题目

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:
Input:  s: "cbaebabacd" p: "abc"
Output:  [0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:
Input:  s: "abab" p: "ab"
Output:  [0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

解析

此题要求找出s串中和p串一致的所有位置，在匹配的过程中不要求一致，任何一个p串的排列组合在s串中有匹配即算是一个结果。
对于这种无序的题目，通常使用的方法是构建Hash，对比字符出现的次数进行匹配。本题要编写的过程中要注意，能提前剔除的情况要除去，否则会造成Time exceed limit。

代码（C语言）

bool is2HashEqual(int* sHash, int* pHash);
int* findAnagrams(char* s, char* p, int* returnSize) {
    if (!s || !p)
        return NULL;
    
    int sLen = (int)strlen(s), pLen = (int)strlen(p);
    if (sLen < pLen)
        return NULL;
    
    int* pHash = (int*)calloc(26, sizeof(int));
    int* sHash = (int*)calloc(26, sizeof(int));
    
    int* returnArr = (int*)calloc(sLen, sizeof(int));
    (*returnSize) = 0;
    
    for (int i = 0; i < pLen; ++i) {
        ++pHash[p[i] - 'a'];
        ++sHash[s[i] - 'a'];
    }
    
    for (int i = 0; i <= sLen - pLen; ++i) {
        if (i != 0) {
            ++sHash[s[i + pLen - 1] - 'a'];
        }
        
        if (is2HashEqual(sHash, pHash)) {
            returnArr[(*returnSize)++] = i;
        }
        
        --sHash[s[i] - 'a'];
    }
    
    free(pHash);
    free(sHash);
    
    return returnArr;
}

bool is2HashEqual(int* sHash, int* pHash) {
    for (int i = 0; i < 26; ++i) {
        if (sHash[i] != pHash[i])
            return false;
    }
    
    return true;
}

这里，笔者使用了滑动窗口的做法。先把最开始pLen长度的进行匹配，然后依次向后一个窗口，再次进行匹配。这里循环执行的长度<= sLen-pLen，这里需要有等于，边界情况要考虑到。