MENU

LeetCode438. Find All Anagrams in a String(滑动窗口)

2019 年 02 月 06 日 • 阅读: 1209 • LeetCode阅读设置

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:cbaebabacdp: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日 星期四
最后编辑于: 2019 年 02 月 14 日