[数据结构与算法]Leetcode438. 找到字符串中所有字母异位词

Every day a leetcode

题目来源：438. 找到字符串中所有字母异位词

解法：滑动窗口+hash

异位词 指由相同字母重排列形成的字符串（包括相同的字符串），其特点为hash表完全一致。

建立两个hash表，hash_p统计p，hash_window统计滑动窗口。

滑动窗口大小windowSize=p的长度。

窗口从s的第一个字符开始， 直到移动至s的末尾。

对每个滑动窗口更新hash_window，再与hash_p匹配，若完全一致，说明当前窗口的字符串是一个异位词，在ans动态数组内增加当前下标；若不一致，窗口右移一位。

函数isMatch()判断hash_p和hash_window是否完全一致。

代码：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 #define MAX_HASH_LENGTH 26

//判断hash_p与hash_window是否一致
bool isMatch(int *hash_p,int *hash_window)
{
    for(int i=0;i<MAX_HASH_LENGTH;i++)
    {
        if(hash_p[i]!=hash_window[i]) return false;
    }
    return true;
}

int* findAnagrams(char * s, char * p, int* returnSize){
    int s_length=strlen(s);
    int p_length=strlen(p);
    int windowSize=p_length;
    *returnSize=0;
    int *ans;
    ans=(int*)malloc(s_length*sizeof(int));

    if(s_length<p_length) return ans;

    int hash_p[MAX_HASH_LENGTH];
    int hash_window[MAX_HASH_LENGTH];
    memset(hash_p,0,sizeof(hash_p));
    memset(hash_window,0,sizeof(hash_window));
    //求p的hash表hash_p
    for(int i=0;i<p_length;i++) hash_p[p[i]-'a']++;
    //开滑
    for(int i=0;i<=s_length-windowSize;i++)
    {
        //先将hash_window还原
        memset(hash_window,0,sizeof(hash_window));
        //求当前滑动窗口的hash表hash_window
        for(int j=0;j<windowSize;j++) hash_window[s[i+j]-'a']++;
        //若hash_p与hash_window一致,ans数组记录当前下标
        if(isMatch(hash_p,hash_window)) ans[*returnSize++]=i;
    }
    return ans;
}

结果：

看起来，运算次数过大，栈爆了…

优化

问题出在对每个滑动窗口都从新开始求hash_window，我们只需要删掉旧窗口开头的hash值，增加新窗口结尾的hash值，即可得到新窗口的hash_window。

代码：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int sLen = s.size(), pLen = p.size();

        if (sLen < pLen) {
            return vector<int>();
        }

        vector<int> ans;
        vector<int> sCount(26);
        vector<int> pCount(26);
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s[i] - 'a'];
            ++pCount[p[i] - 'a'];
        }

        if (sCount == pCount) {
            ans.emplace_back(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s[i] - 'a'];
            ++sCount[s[i + pLen] - 'a'];

            if (sCount == pCount) {
                ans.emplace_back(i + 1);
            }
        }

        return ans;
    }
};

结果：