LeetCode438. Find All Anagrams in a String（滑动窗口）

Easy
Accepted：102,812
Submissions：285,887

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".

链接

https://leetcode.com/problems/find-all-anagrams-in-a-string/

题意

给定两个字符串s和p，找到p的所有anagrams在s中出现的开始位置。anagrams的意思是由颠倒字母顺序而构成的字，也就是abc/acb/bac/bca/cab/cba算同一个p。字符串均由小写字母组成且s和p的长度都不会超过20100。

题解

假设s长度为n，p长度为m。

暴力，时间复杂度$O((n-m)*m)$，n-m找到所有“可能的p”，m进行匹配看是否为p的anagrams。
匹配的话我们可以使用哈希表，用一个数组来统计p中所有字母出现的数量，cnt[p[i]]++，如果某个字母匹配上的话可以cnt[s[i]]--，统计是否完全匹配完成即可。
滑动指针，时间复杂度$O(n)$，对s遍历一次，在遍历的过程中动态的与p进行匹配。初始化l和r均指向0位置，cnt数组统计p中所有字母的数量，len为p的长度，对于当前字母s[r++]如果在p中，则cnt中当前字母数量减1，len-1，当len为0时表示成功完成一次匹配，当r-l等于p的长度时完成第一次寻找，整体右移，如果当前字母s[l++]在p中时，len+1，相当于“对cnt数组复原”接着判断。（cnt值为>=0为p中字符）
s:cbaebabacd，p:abc，$\overline{cba}ebabacd \rightarrow c\overline{bae}babacd \rightarrow cb\overline{aeb}abacd...$

代码

Runtime: 32 ms, faster than 53.09% of C++ online submissions for Find All Anagrams in a String.
Memory Usage: 7 MB, less than 0.89% of C++ online submissions for Find All Anagrams in a String.

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int cnt[256] = {0};
        int n = s.length(), m = p.length();
        int l = 0, r = 0, len = m; // 滑动窗口为s[l r)
        vector <int> ans;
        for (int i = 0; i < m; ++i) // “哈希”存储
            cnt[p[i]]++;
        while (r < n)
        {
            if (cnt[s[r++]]-- >= 1) // 该字母在p中
                --len;
            if (len == 0) // 符合要求
                ans.push_back(l);
            if (r - l == m && cnt[s[l++]]++ >= 0) // 整体右移
                ++len;
        }
        return ans;
    }
};

一种看上去更好的写法

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector <int> scnt(26, 0);
        vector <int> pcnt(26, 0);
        vector <int> ans;
        int n = s.length(), m = p.length();
        int l = 0, r = 0;
        for (int i = 0; i < m; ++i)
            ++pcnt[p[i] - 'a'];
        for (int i = 0; i < n; ++i)
        {
            if (i >= l) // 整体右移
                --scnt[s[i - m] - 'a'];
            ++scnt[s[i] - 'a'];
            if (scnt == pcnt) // 相等时完成匹配
                ans.push_back(i - m + 1);
        }
        return ans;
    }
};

To be continued.
2019年2月7日星期四