【Day 45 】2021-10-24 - 438. 找到字符串中所有字母异位词

[azl397985856]

438. 找到字符串中所有字母异位词

入选理由

暂无

题目地址

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

前置知识

• Sliding Window
• 哈希表

  题目描述

  
  给定一个字符串 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" 的字母异位词。

[yanglr]

思路:

分析一下，首先题中说找到 s 中所有是 p 的字母异位词(假如p1 的字母异位词是p2, 两个字符串p1、p2包含的各种字母数量都相等)的子串，就这句话，就包含了如下两个重要信息：

• 找到的符合要求的子串长度都是 p
• 什么是字母异位词？也就是我们不关心 p 这个串的顺序，只关心字母是否出现以及出现的次数，这种问题解决方案一般有两种，一种是利用排序强制顺序，另一种就是用哈希表的方法。

方法: 滑动窗口 + 数组模拟哈希表

本题，我们可以用固定宽度的滑动窗口来做。

那么用什么数据结构来记录窗口中各个字母出现的次数呢？哈希表是比较一个比较符合直觉的想法。

还有一种就是用数组。因为字符串中只包含小写字母，也就是只有 26 种字母，所以我们可以使用一个长度为 26 的数组来记录，数组下标表示字母，值则表示字母出现的次数。

代码:

实现语言: C++

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res; /* 存放这些子串的起始索引startPos */
        int restCount = p.size(); /* 维护一个固定长度的窗口, 窗口长度 = len(p), restCount: 剩下的待匹配字符的数量 */
        vector<int> pFreq(26); /* 模拟一个计数哈希表 */
        for (int i = 0; i < p.size(); i++)
            pFreq[p[i] - 'a']++;
        vector<int> sFreq(26); /* 模拟一个计数哈希表, sFreq: 字符串s中处于滑动窗口内的字符的频次 */
        for (int i = 0; i < s.size(); i++)
        {
            char c = s[i];
            sFreq[c - 'a']++; /* 向窗口末尾加入1个新字符 */
            if (sFreq[c - 'a'] <= pFreq[c - 'a']) /* 当前窗口中这个字符的数量还没到上限, 可以成功加入 */
                restCount--;
            if (i >= p.size()) /* 删除原窗口最前面的那1个字符, 最新的startPos = i - len(p) + 1, 那么上一次的startPos = i - p.size() */
            {
                char h = s[i - p.size()]; /* h: 上一轮中窗口中最前面的字符 */
                sFreq[h - 'a']--;
                if (sFreq[h - 'a'] < pFreq[h - 'a'])
                    restCount++;
            }
            // 字符都匹配完成, 表示是一个有效的字母异位词(anagram)
            if (restCount == 0) /* i - startPos + 1 = len(p) => startPos = i - len(p) + 1 */
                res.push_back(i - p.size() + 1);
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[cassiechris]

思路

学习官方题解

代码

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        target = collections.Counter(p)
        ans = []
        for i in range(len(s)):
            if i >= len(p):
                target[s[i - len(p)]] += 1
                if target[s[i - len(p)]] == 0:
                    del target[s[i - len(p)]]
            target[s[i]] -= 1
            if target[s[i]] == 0:
                del target[s[i]]
            if len(target) == 0:
                ans.append(i - len(p) + 1)
        return ans

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(1)

[xj-yan]

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int[] pattern = new int[26];
        for (char c : p.toCharArray()){
            pattern[c - 'a']++;
        }
        int[] window = new int[26];
        int pLen = p.length();
        String patternStr = Arrays.toString(pattern);

        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            window[c - 'a']++;
            if (i - pLen >= 0) window[s.charAt(i - pLen) - 'a']--;
            if (i - pLen + 1 >= 0){
                if (Arrays.toString(window).equals(patternStr)){
                    result.add(i - pLen + 1);
                }
            }
        }
        return result;
    }
}

Time Complexity: O(n + m) => n : the length of s, m : the length of p Space Complexity: O(1)

[ZacheryCao]

Idea:

Sliding window + Hash table. The window's size is the length of pattern string. Increase the left side and right side of the sliding window by1 at every step. Then check whether the new window's substring has same char frequency as pattern string.

Code:

from collections import Counter
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        p_count = Counter(p)
        cur_count = Counter()
        l, r = 0, 0
        ans = []
        if len(p) > len(s):
            return ans
        while r < len(p):
            if s[r] in p_count:
                cur_count[s[r]] = cur_count.get(s[r], 0) + 1
            r += 1
        if cur_count == p_count:
            ans.append(l)
        while r < len(s):
            if s[r] in p_count:
                cur_count[s[r]] = cur_count.get(s[r], 0) + 1
            r += 1
            if s[l] in p_count:
                cur_count[s[l]] -= 1
            l += 1
            if cur_count == p_count:
                ans.append(l)
        return ans

Complexity:

Time: O(N). N is length of s + length of p. We pass s and p by once. The comparison between two counters is O(26), since it only has 26 distinct lowercase letters Space: O(1). The max length of counter is O(26), same reason as its time complexity.

[Daniel-Zheng]

思路

滑动窗口 + 数组模拟哈希表。

代码(C++)

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        if (s.size() < p.size()) return res;
        vector<int> slideWindowS(26);
        vector<int> slideWindowP(26);
        for (int i = 0; i < p.size(); i++) slideWindowP[p[i] - 'a']++;
        int left = 0;
        for (int right = 0; right < s.size(); right++) {
            slideWindowS[s[right] - 'a']++;
            if (right >= p.size()) slideWindowS[s[left++] - 'a']--;
            if (slideWindowS == slideWindowP) res.push_back(left);
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)

[ZiyangZ]

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        Map<Character, Integer> map = new HashMap<>();
        for (char c: p.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        int left = 0;
        int right = 0;
        for (; right < s.length(); right++) {
            char l = s.charAt(left);
            char r = s.charAt(right);
            if (right >= p.length()) {
                if (map.containsKey(l)) map.put(l, map.get(l) + 1);
                else map.put(l, 1);
                if (map.get(l) == 0) map.remove(l);
                left++;
            }
            if (map.containsKey(r)) map.put(r, map.get(r) - 1);
            else map.put(r, -1);
            if (map.get(r) == 0) map.remove(r);

            if (map.size() == 0) ans.add(left);
        }
        return ans;
    }
}

[falconruo]

思路: 固定长度的滑动窗口 + 辅助数组或hash

复杂度分析:

• 时间复杂度: O(n + m)，其中n是字符串s的长度, m是字符串p的长度
• 空间复杂度: O(1), 常数级辅助空间

代码 (C++):

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if (s.length() < p.length()) return {};

        vector<int> dictP(26, 0);
        vector<int> dictA(26, 0);

        for (auto c : p)
            dictP[c - 'a']++;

        vector<int> res;
        int k = p.length();
        for (int i = 0; i < s.length(); ++i) {
            if (i - k >= 0) { // fixed length = k sliding windows [0, k - 1]
                dictA[s[i - k] - 'a']--;
            }

            dictA[s[i] - 'a']++;
            if (dictA == dictP)
                res.push_back(i - k + 1);
        }

        return res;
    }
};

[yachtcoder]

Sliding window.

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        l, N, M = 0, len(s), len(p)
        counter = Counter()
        cs = Counter(p)
        ret = []
        k = 0
        for r in range(N):
            c = s[r]
            counter[c] += 1
            if counter[c] == cs[c]: k += 1
            while r - l + 1 > M:
                counter[s[l]] -= 1
                if counter[s[l]] == cs[s[l]] - 1:
                    k -= 1
                l += 1
            if k == len(cs):
                ret.append(l)
        return ret

[heyqz]

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        res = []
        n, m = len(s), len(p)
        count = Counter(p)
        window = Counter(s[:m - 1])

        for i in range(m - 1, n):
            window[s[i]] += 1   # add next char to the window
            if window == count:    
                res.append(i - m + 1) 
            window[s[i - m + 1]] -= 1   # decrease the count of oldest char in the window
            if window[s[i - m + 1]] == 0:
                del window[s[i - m + 1]]
        return res

time complexity: O(n) space complexity: O(1)

[tongxw]

思路

固定长度滑动窗口。计数统计窗口内字符个数并且和给定短字符串对比。

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int m = s.length();
        int n = p.length();
        if (m < n) {
            return new ArrayList<>();
        }

        int[] charsInP = new int[26]; // SC: O(1)
        for (int i=0; i<n; i++) { // O(n)
            charsInP[p.charAt(i) - 'a'] += 1;
        }

        int[] charsInWindow = new int[26]; // SC: O(1)
        for (int i=0; i<n-1; i++) { // O(n)
            charsInWindow[s.charAt(i) - 'a'] += 1;
        }

        List<Integer> ans = new ArrayList<>();
        for (int i=n-1; i<m; i++) { // O(m)
            // add the char at right index
            charsInWindow[s.charAt(i) - 'a'] += 1;

            // check
            if (isAnagram(charsInP, charsInWindow)) { // O(1)
                // left index
                ans.add(i - n + 1);
            }

            // remove the char at left index
            charsInWindow[s.charAt(i - n + 1) - 'a'] -= 1;
        }

        return ans;
    }

    private boolean isAnagram(int[] chars1, int[] chars2) {
        for (int i=0; i<26; i++) {
            if (chars1[i] != chars2[i]) {
                return false;
            }
        }

        return true;
    }
}

TC: O(len(s) + len(p)) SC: O(1)

[comst007]

438. 找到字符串中所有字母异位词

---

思路

滑动窗口

代码

• C++

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> p_cnt(26, 0), s_cnt(26, 0);

        for(auto cc: p){
            p_cnt[cc - 'a'] ++;
        }
        int cur_cnt;
        vector<int> ans;
        int ii, jj;
        int last_idx, cur_idx;

        int k = p.size();
        cur_cnt = 0;

        for(ii = 0, jj = 0; ii < s.size(); ++ ii){
            if(ii >= k){
                last_idx = s[jj] - 'a';
                if(p_cnt[last_idx]){

                    s_cnt[last_idx] --;
                    if(s_cnt[last_idx] < p_cnt[last_idx]){
                        -- cur_cnt;
                    }
                }
                ++ jj; 
            }
            cur_idx = s[ii] - 'a';
            if(p_cnt[cur_idx]){
                s_cnt[cur_idx] ++;
                if(s_cnt[cur_idx] <= p_cnt[cur_idx]){
                    cur_cnt ++;
                }

            }
            if(cur_cnt == k){
                ans.push_back(ii - k + 1);
            }
        }
        return ans;
    }
};

---

复杂度分析

n为字符串S长度， k为字符串P长度。

• 时间复杂度 O(n + k)。
• 空间复杂度 O(1)。

[qyw-wqy]

···java class Solution { public List findAnagrams(String s, String p) { List list = new ArrayList<>(); int[] counts = new int[26];
for (char c : p.toCharArray()) { counts[c - 'a']++; } int count = p.length(); for (int l = 0, r = 0; r < s.length(); r++) { if (counts[s.charAt(r) - 'a']-- > 0) { count--; } while (counts[s.charAt(r) - 'a'] < 0) { if (counts[s.charAt(l++) - 'a']++ >= 0) count++; } if (count == 0) { list.add(l); } } return list; } }

Time: O(n)\
Space: O(1)

[siyuelee]

Sliding window and a list (length is 26)

class Solution(object):
    def findAnagrams(self, s, p):

        n, m, res = len(s), len(p), []
        if n < m: return res
        p_cnt = [0] * 26
        s_cnt = [0] * 26
        for i in range(m):
            p_cnt[ord(p[i]) - ord('a')] += 1
            s_cnt[ord(s[i]) - ord('a')] += 1
        if s_cnt == p_cnt:
            res.append(0)

        for i in range(m, n):
            s_cnt[ord(s[i - m]) - ord('a')] -= 1
            s_cnt[ord(s[i]) - ord('a')] += 1
            if s_cnt == p_cnt:
                res.append(i - m + 1)
        return res

T: O(n), for loop is O(n) and comparison between two list is O(26) S: O(1)

[mmboxmm]

思路

滑动窗口

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s.length() < p.length()) return res;

        int[] map = new int[26];
        int cnt = 0;
        for (char c : p.toCharArray()) {
            if (map[c - 'a'] == 0) cnt++;
            map[c - 'a']++;
        }

        for (int i = 0;  i < s.length(); i++) {
            char c = s.charAt(i);
            map[c - 'a']--;
            if (map[c - 'a'] == 0) cnt--;

            if (i >= p.length()) {
                char d = s.charAt(i - p.length());
                if (map[d - 'a'] == 0) cnt++;
                map[d - 'a']++;
            }

            if (cnt == 0) res.add(i + 1 - p.length());
        }
        return res;
    }
}

复杂度

• Time: O(n)

[pophy]

思路

• 定长滑动窗口
• 用两个词频统计表 分别表示当前窗口w 和 p的词频 sCount, pCount
  • 如果sCount 和 pCount相同 则表示当前窗口合法

Java Code

    public List<Integer> findAnagrams(String s, String p) {
        int m = s.length(), n = p.length();
        if (m < n) {
            return new ArrayList();
        }
        List<Integer> res = new ArrayList<>();
        int[] pCount = new int[26];
        for (char c : p.toCharArray()) {
            pCount[c - 'a']++;
        }
        int[] sCount = new int[26];
        for (int i = 0; i < m; i++) {
            char cur = s.charAt(i);
            sCount[cur - 'a']++;
            if (i >= n) {
                sCount[s.charAt(i - n) - 'a']--;
            }
            if (Arrays.equals(pCount, sCount)) {
                res.add(i - n);
            }
        }
        return res;
    }

时间&空间

• 时间 O(n^2)
• 空间 O(1)

[xieyj17]

from collections import Counter

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        p_dict = Counter(p)
        res = []
        td = Counter(s[0:len(p)])
        if td == p_dict:
                res.append(0)
        left = 1
        right = len(p)
        while right < len(s):
            if td[s[left-1]] > 1:
                td[s[left-1]] -= 1
            else:
                del td[s[left-1]]        
            if s[right] in td:
                td[s[right]] += 1
            else:
                td[s[right]] = 1
            if td == p_dict:
                res.append(left)
            left += 1
            right += 1

        return res

-Maintain a dictionary of chars in rolling window.

-In each step remove the left most char and add the one next to the right most char.

-Compare the dictionary of rolling window with dictionary of p

Space: O(len(p))

Time: O(N)

[laofuWF]

# sliding window
# keep a count of valid letters in current sliding window
# every time right index moves, check if count == len(p), and add to res
# 3 cases when right index move
# 1. letter in p and hasn't reached total num of p: increment count, update dict
# 2. letter not in p, move left to right + 1, refresh all (count, dict)
# 3. letter in p but went over boundary: move left until first current letter is removed from the left

# time: O(N), length of s
# space: O(M), number of unique letters in p

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        original_letters = collections.defaultdict(int)

        for letter in p:
            original_letters[letter] += 1

        if len(s) < len(p):
            return []

        left = 0
        # number of valid letters in current sliding window
        count = 0
        res = []

        letters = original_letters.copy()
        for right in range(len(s)):
            if s[right] in letters and letters[s[right]] > 0:
                count += 1
                letters[s[right]] -= 1
            elif not s[right] in letters :
                left = right + 1
                count = 0
                letters = original_letters.copy()
            else:
                # too many number of letter s[right] in the window
                # remove letter from left
                while s[left] != s[right]:
                    if s[left] in letters:
                        count -= 1
                        letters[s[left]] += 1
                    left += 1
                left += 1

            if count == len(p):
                res.append(left)

        return res

[cicihou]

from collections import Counter

class Solution:
    def findAnagrams(self, s: str, p: str) -> list:
        ''' method 1 '''
        counter = Counter(p)
        res = []
        for i in range(len(s) - len(p) + 1):
            if Counter(s[i:i + len(p)]) == counter:
                res.append(i)
        return res

        ''' method 2 
        much more faster than method 1
        time: O(n)
        space: O(n)

        我们比较两个 hashmap 理论上来说应该是 O(n)，但是由于本题的 hashmap 最多只会有 26 个字母，所以是 O(1)
        '''
        counter = Counter(p)
        res = []

        tmp = Counter(s[:len(p)])

        for i in range(len(p), len(s)+1):
            if tmp == counter:
                res.append(i-len(p))
            if i == len(s):
                return res

            # modify the tmp
            tmp[s[i-len(p)]] -= 1
            tmp[s[i]] = tmp.get(s[i], 0) + 1
            if tmp[s[i-len(p)]] == 0:
                tmp.pop(s[i-len(p)])
        return res

s = Solution()
s.findAnagrams('abab', 'ab')

[Zhi22]

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        p_dict = Counter(p)
        res = []
        td = Counter(s[0:len(p)])
        if td == p_dict:
                res.append(0)
        left = 1
        right = len(p)
        while right < len(s):
            if td[s[left-1]] > 1:
                td[s[left-1]] -= 1
            else:
                del td[s[left-1]]        
            if s[right] in td:
                td[s[right]] += 1
            else:
                td[s[right]] = 1
            if td == p_dict:
                res.append(left)
            left += 1
            right += 1

        return res

[chang-you]

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s == null || p == null || s.length() < p.length()) return res;
        int[] chars = new int[26];
        for (char c : p.toCharArray()) {
                chars[c - 'a']++;
        }
        int start = 0, end = 0;
        int count = p.length();
        while (end < s.length()) {
            if (end - start ==  p.length() && chars[s.charAt(start++) - 'a']++ >= 0) {

                count++;
            }

            if (--chars[s.charAt(end++) - 'a'] >= 0) {

                count--;
            } 

            if (count == 0) res.add(start);

        }
        return res;
    }
}

[chen445]

思路

Using sliding window and hashmap

代码

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(p) > len(s):
            return []
        result=[]
        values=defaultdict(int)
        for i in p:
            values[i]+=1
        left=0
        for right in range(len(s)):
            if right>=len(p):
                values[s[left]]+=1
                left+=1
            values[s[right]]-=1   
            if self.is_all_zero(values):
                result.append(left)
        return result
    def is_all_zero(self,values):
        for value in values:
            if values[value] !=0:
                return False
        return True

复杂度

Time: O(n)

Space: O(1)

[nonevsnull]

思路

• 拿到题的直觉解法
  • 题目不难，但是实现很慢，说明写代码不熟；
  • 看起来会，一旦写起来有各种点，发现都没考虑到，不停地卡住；
  • 这是写少了，经验不足的体现；
  • 此题bf可以通过，每次都用窗口中的和p做暴力匹配
  • 优化的解法用到map和双指针

AC

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        HashMap<Character, Integer> mapP = new HashMap<>();

        for(char c: p.toCharArray()){
            mapP.putIfAbsent(c, 0);
            mapP.put(c, mapP.get(c)+1);
        }

        HashMap<Character, Integer> mapS = new HashMap<>();
        List<Integer> res = new ArrayList<>();
        for(int i = 0;i < s.length();i++){
            char cur = s.charAt(i);

            mapS.putIfAbsent(cur, 0);
            mapS.put(cur, mapS.get(cur)+1);

            if(i >= p.length()) {
                int first = i - p.length();
                char firstChar = s.charAt(first);

                mapS.put(firstChar, mapS.get(firstChar)-1);
                if(mapS.get(firstChar) == 0) mapS.remove(firstChar);
            }

            if(mapS.equals(mapP)) res.add(i - p.length() + 1);
        }
        return res;

    }
}

复杂度

//优化解 time: O(S+P) space: O(1)

[yiwchen]

思路： Sliding + hash

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:

        p_count = collections.Counter(p)
        s_count = collections.Counter(s[0: len(p)])
        i = lp = len(p)
        ls = len(s)
        res = []
        while i < len(s):
            if not p_count - s_count:
                res.append(i - lp)
            s_count[s[i - lp]] -= 1
            s_count[s[i]] += 1
            i += 1
        if not p_count - s_count:
            res.append(i - lp)
        return res

晚点回来续写……

[Moin-Jer]

思路

---

使用滑动窗口进行字符串匹配，通过将字符信息存储到哈希表中，如果新加入的字符不满足条件，则不断移动左指针， 直到滑动窗口中的字符满足条件，此时判断满足条件的字符与目标字符个数是否相等

代码

---

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        char[] chs = s.toCharArray();
        char[] chp = p.toCharArray();
        int[] target = new int[26];
        for (char ch : chp) {
            ++target[ch - 'a'];
        }
        int[] cur = new int[26];
        int l = 0, r = 0;
        while (r < chs.length) {
            ++cur[chs[r] - 'a'];
            while (cur[chs[r] - 'a'] > target[chs[r] - 'a']) {
                --cur[chs[l] - 'a'];
                ++l;
            }
            if (r - l + 1 == chp.length) {
                ans.add(l);
            }
            ++r;
        }return ans;
    }
}

复杂度分析

---

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[thinkfurther]

思路

使用dict记录出现的频率，使用滑动窗口寻找匹配

代码

class Solution:
    def findAnagrams(self, s: str, p: str) :
        if len(s) < len(p):
            return []

        result = []
        targetDict = collections.defaultdict(int)
        for c in p:
            targetDict[c] += 1

        sDict = collections.defaultdict(int)
        slow = 0
        for fast in range(len(s)):
            if fast < len(p):
                if s[fast] in targetDict:
                    sDict[s[fast]] += 1
                if targetDict == sDict:
                    result.append(slow)
                continue                

            if s[slow] in targetDict:
                sDict[s[slow]] -= 1
            slow += 1
            if s[fast] in targetDict:
                sDict[s[fast]] += 1

            if targetDict == sDict:
                result.append(slow)

        return result

复杂度

时间复杂度 ：O(n)

空间复杂度：O(1)

[vincentLW]

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s.length() < p.length()) return res;

        int[] map = new int[26];
        int cnt = 0;
        for (char c : p.toCharArray()) {
            if (map[c - 'a'] == 0) cnt++;
            map[c - 'a']++;
        }

        for (int i = 0;  i < s.length(); i++) {
            char c = s.charAt(i);
            map[c - 'a']--;
            if (map[c - 'a'] == 0) cnt--;

            if (i >= p.length()) {
                char d = s.charAt(i - p.length());
                if (map[d - 'a'] == 0) cnt++;
                map[d - 'a']++;
            }

            if (cnt == 0) res.add(i + 1 - p.length());
        }
        return res;
    }
}

时间复杂度 ：O(n)

空间复杂度：O(1)

[LAGRANGIST]

class Solution { public: vector findAnagrams(string s, string p) { vector res; / 存放这些子串的起始索引startPos / int restCount = p.size(); / 维护一个固定长度的窗口, 窗口长度 = len(p), restCount: 剩下的待匹配字符的数量 / vector pFreq(26); / 模拟一个计数哈希表 / for (int i = 0; i < p.size(); i++) pFreq[p[i] - 'a']++; vector sFreq(26); / 模拟一个计数哈希表, sFreq: 字符串s中处于滑动窗口内的字符的频次 / for (int i = 0; i < s.size(); i++) { char c = s[i]; sFreq[c - 'a']++; / 向窗口末尾加入1个新字符 / if (sFreq[c - 'a'] <= pFreq[c - 'a']) / 当前窗口中这个字符的数量还没到上限, 可以成功加入 / restCount--; if (i >= p.size()) char h = s[i - p.size()]; / h: 上一轮中窗口中最前面的字符 / sFreq[h - 'a']--; if (sFreq[h - 'a'] < pFreq[h - 'a']) restCount++; }

        if (restCount == 0) /* i - startPos + 1 = len(p) => startPos = i - len(p) + 1 */
            res.push_back(i - p.size() + 1);
    }
    return res;
}

};

[james20141606]

Day 45: 438. Find All Anagrams in a String (sliding window, string)

• Problem Link

  • 438. Find All Anagrams in a String

• Ideas

  • loop through s and use counter to compare with p
  • to optimize, only update the first and last char in the sliding window. Note the dict should have same keys to make sure the comparison is correct.

• Complexity: hash table and bucket

  • Time: O(N)
  • Space: O(1)

• Code

from collections import Counter
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        counter_p = Counter(p)
        ans = []
        for i in range(len(s) - len(p) + 1):
            if Counter(s[i:i+len(p)]) == counter_p:
                ans.append(i)
        return ans

#not some value=0 may lead to mismatch which is wrong, 
#set(s) + set(p)
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        counter_p = {key: 0 for key in set(s+p)} #Counter(p)
        counter_cur = {key: 0 for key in set(s+p)}#Counter(s[:len(p)])
        for character in p:
            counter_p[character] += 1
        for character in s[:len(p)]:
            counter_cur[character] += 1
        if counter_cur == counter_p:
            ans = [0]
        else:
            ans = []
        for i in range(1, len(s) - len(p) + 1):
            #print (i, counter_cur, s[i - 1], s[i + len(p) -1])
            counter_cur[s[i - 1]] -= 1
            counter_cur[s[i + len(p) -1]] += 1
            if counter_cur == counter_p:
                ans.append(i)
        return ans

• other resources:

[chenming-cao]

解题思路

滑动窗口。用长度为26的数组记录字符串p中每个字符出现的次数。然后设置宽度为字符串长度p.length()的滑动窗口，求出字符串s在滑动窗口内的各个字符串出现次数，记录到数组中。如果该数组和字符串p的数组相等，则表示异位词出现。

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int slen = s.length();
        int plen = p.length();
        List<Integer> res = new ArrayList<>();
        if (slen < plen) return res;
        int[] letters = new int[26];
        for (char c : p.toCharArray()) {
            letters[c - 'a']++;
        }
        String pletters = Arrays.toString(letters);     
        int[] word = new int[26];
        for (int i = 0; i < plen; i++) {
            word[s.charAt(i) - 'a']++;
        }
        if (Arrays.equals(letters, word)) res.add(0);
        for (int i = 1; i <= slen - plen; i++) {
            int pre = s.charAt(i - 1) - 'a';
            int post = s.charAt(i + plen - 1) - 'a';
            word[pre]--;
            word[post]++;
            if (Arrays.equals(letters, word)) res.add(i);
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n)，n为s的长度
• 空间复杂度：O(1)，需要两个长度为26的数组

[Francis-xsc]

思路

滑动窗口，用哈希表记录字母

代码

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int len=p.size(),slen=s.size();
        vector<int> res;
        if(s.size()<len)
            return {};
        unordered_map<char,int>a,b;
        for(char c : p)
            b[c]++;
        int l=0,r=0;
        for(r=0;r<len;r++)
            a[s[r]]++;
        --r;
        while(r<slen)
        {
            if(a==b)
                res.push_back(l);
            a[s[l]]--;
            if(a[s[l]]==0)
            {
                a.erase(s[l]);
            }
            l++;
            r++;
            a[s[r]]++;
        };
        return res;
    }
};

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[yan0327]

思路: 这道题以为之前做过可以立马AC，结果还是不行。 感觉还是需要区分一下什么时候调用计数函数，什么时候直接滑动窗口。 这题可以对不符合要求的直接左移窗口，当长度与目标长度相同时插入数据

func findAnagrams(s string, p string) []int {
    out := []int{}
    want := [26]int{}
    have := [26]int{}
    if len(s) < len(p){
        return nil
    }
    for _,x := range p{
        want[x-'a']++
    }
    l:=0
   for r:= range s{
       have[s[r]-'a']++
       for have[s[r]-'a'] > want[s[r]-'a']{
           have[s[l]-'a']--
           l++
       }
       if r-l+1 == len(p){
           out = append(out,l)
       }
   }
   return out
}

时间复杂度O（n） 空间复杂度O（1）

[xjlgod]

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int sLen = s.length(), pLen = p.length();
        if (pLen > sLen) {
            return res;
        } 
        Map<Character, Integer> map = new HashMap<>();
        // 记录窗口中能与map匹配的字符
        Map<Character, Integer> window = new HashMap<>();
        // 初始化p里对应的所有字符
        for (int i = 0; i < pLen; i++) {
            map.put(p.charAt(i), map.getOrDefault(p.charAt(i), 0) + 1);
        }
        // valid记录window中有几个字符的数类与map中的匹配
        int left = 0, right = 0, valid = 0, count = map.size();
        // 滑动窗口开始滑动
        while (right < sLen) {
            char key = s.charAt(right);
            // 如果新字符在窗口内则更新
            if (map.containsKey(key)) {
                window.put(key, window.getOrDefault(key, 0) + 1);
                // 计算在已经valid的情况下，这个key的所属数量又变了也不影响，因为必须所有字符同时达到要求
                if (window.get(key).equals(map.get(key))) {
                    valid++;
                }
            }
            // 窗口更新
            if (right - left + 1 == pLen) {
                // 符合定义添加
                if (valid == count) {
                    res.add(left);
                }
                char l = s.charAt(left);
                if (map.containsKey(l)) {
                    if (window.get(l).equals(map.get(l))) {
                        valid--;
                    }
                    window.put(l, window.get(l) - 1);
                }
                left++;
            }
            right++;
        }
        return res;
    }
}

[leo173701]

思路：

1. 利用哈希表统计各个字符的频数
2. 固定窗口的滑动窗口问题
3. 适当删除 哈希表当中的元素

class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: target = collections.Counter(p) k = len(p) temp = collections.Counter(s[:k]) res = [] if temp== target: res.append(0) for i in range(1,len(s)-k+1):
temp[s[i+k-1]] = temp.get(s[i+k-1],0)+1 temp[s[i-1]] -=1 if temp[s[i-1]]==0: del temp[s[i-1]] if temp == target:

print(s[i:i+k])

            # print(temp)
            res.append(i)
    return res

[joeytor]

思路

先使用 count 统计 p 中 char 的个数

遍历 string s

​ 每次 将 s[i] 从 count 中消去, 如果消去后 count 为 0, 那么在 count 中删除这个 key

​ 如果 i≥lp 时, 滑动窗口开始

​ 将滑出窗口的 s[i-lp] 在 count 中 +1 (因为之前被消去了)

​ 此时如果 +1 后 count 为 0, 那么在 count 中删除这个 key

​ 当 len(count) == 0 时, 代表所有元素正好都能跟 p 中元素消去, 那么将 i-lp+1 即滑动窗口的左边界加入 res 数组

from collections import defaultdict, Counter
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        count = Counter(p)
        ls, lp = len(s), len(p)
        res = []
        for i in range(ls):
            count[s[i]] -= 1
            if count[s[i]] == 0:
                del count[s[i]]
            if i >= lp:
                count[s[i-lp]] += 1
                if count[s[i-lp]] == 0:
                    del count[s[i-lp]]
            if len(count) == 0:
                res.append(i-lp+1)

        return res

复杂度

时间复杂度: O(n) 遍历一次数组的复杂度

空间复杂度: O(1) count 哈希表的复杂度不会超过 O(26) 因为只有 26 个字符, 所以还是常数级别空间

[Serena9]

代码

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        target = collections.Counter(p)
        ans = []
        for i in range(len(s)):
            if i >= len(p):
                target[s[i - len(p)]] += 1
                if target[s[i - len(p)]] == 0:
                    del target[s[i - len(p)]]
            target[s[i]] -= 1
            if target[s[i]] == 0:
                del target[s[i]]
            if len(target) == 0:
                ans.append(i - len(p) + 1)
        return ans

[ychen8777]

思路

滑动窗口 \ int[26] 统计p中每个字母出现的次数\ int[26] 滑动统计 s 的substring 中字母的次数\ 比较两个数组

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {

        List<Integer> res = new ArrayList<>();

        if (s == null || p == null || s.length() < p.length()) {
            return res;
        }

        int sLength = s.length();
        int pLength = p.length();
        int[] target = new int[26];
        int[] curSub = new int[26];

        for (int i = 0; i < pLength; i++) {
            target[p.charAt(i) - 'a']++;
            curSub[s.charAt(i) - 'a']++;
        }

        if (Arrays.equals(target, curSub)) {
            res.add(0);
        }

        for (int i = 1; i <= sLength - pLength; i++) {
            curSub[s.charAt(i-1) - 'a']--;
            curSub[s.charAt(i+pLength-1) - 'a']++;

            if (Arrays.equals(target, curSub)) {
                res.add(i);
            } 

        }

        return res;
    }
}

复杂度

时间: O(n) \ 空间: O(n)

[ghost]

题目

438. Find All Anagrams in a String

思路

Sliding window + Hash Table or Array

代码

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:

        if len(s) < len(p): return []

        res = []
        memo = [0] * 26
        rest = len(p)

        for char in p:
            memo[ord(char) - ord('a')] += 1

        i = 0
        for i in range(len(p)):
            index = ord(s[i]) - ord('a')
            memo[index] -= 1

            if memo[index] >= 0:
                rest -= 1

        if rest == 0: res.append(0)

        i = 0
        for j in range(len(p), len(s)):

            l = ord(s[i]) - ord('a')
            r = ord(s[j]) - ord('a')

            if memo[l] >= 0: 
                rest+=1

            memo[l] += 1

            if memo[r] > 0: 
                rest-=1
            memo[r] -= 1  

            i+=1
            if rest == 0: res.append(i)

        return res

复杂度

Space: O(1) Time: O(len(s))

[lilyzhaoyilu]

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res, hash(26, 0), hashZero(26,0);
        if(s.length() < p.length()) return res;

        for(int i = 0; i < p.length(); i++){
            hash[p[i] - 'a']++;
            hash[s[i] - 'a']--;
        }
        if(hash == hashZero) res.push_back(0);

        for(int i = p.length(); i < s.length(); i++){
            hash[s[i] - 'a']--;
            hash[s[i - p.length()] - 'a']++;
            if(hash == hashZero) res.push_back(i - p.length() + 1);
        }

        return res;
    }
};

[akxuan]

心得

题目并不难, 但是一看上去很唬人. 静下心来先想用什么算法, 分析一下大致时间复杂度, 然后再分析用什么数据结构比较好.

坑

1. slicing window 最好一次过, 不要用多次, 比如这个题, 如果先slicing len(p) 长度, 这个边界就很难判断.

时间复杂度 O(n) 空间是 O(1)

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:

        res = []
        p_dict = {}
        for i in p:
            if i in p_dict :
                p_dict[i] += 1
            else:
                p_dict[i] = 1 

        if len(s) < len(p):
            return []

        s_dict = {}

        for  i in range(len(s)):
            if i < len(p):
                if s[i] in s_dict:
                    s_dict[s[i]] +=1
                else:
                    s_dict[s[i]] =1

            else:

                s_dict[s[i-len(p)] ] -= 1
                if s[i] in s_dict:
                    s_dict[ s[i]] += 1
                else:
                    s_dict[ s[i]] = 1

            flag = True

            for key in p_dict:
                if key in s_dict:
                    if p_dict[key] !=  s_dict[key]:
                        flag = False
                else:
                    flag = False

            if flag:

                res.append(i-len(p)+1)

        return res

[kidexp]

thoughts

滑动窗口 记录需要的letter和对应的个数，以及sliding window里面的在p中letter的个数

遍历数组，如果遇到p中的letter加入sliding window，用一个valid count来记录是不是遍历了所有的letter

然后以len(p)为窗口更新valid count 和 sliding window

code

from collections import defaultdict
from typing import List

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        result = []
        needed_dict, window_dict = defaultdict(int), defaultdict(int)
        for char in p:
            needed_dict[char] += 1
        left = valid_count = 0
        for i, char in enumerate(s):
            if char in needed_dict:
                window_dict[char] += 1
                if window_dict[char] == needed_dict[char]:
                    valid_count += 1
            while i - left + 1 > len(p):
                if s[left] in needed_dict:
                    if window_dict[s[left]] == needed_dict[s[left]]:
                        valid_count -= 1
                    window_dict[s[left]] -= 1
                left += 1
            if valid_count == len(needed_dict):
                result.append(left)
        return result

complexity

time O(n + m) n为s的长度, m为p的长度

Space O(m)

[kendj-staff]

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<Integer>();
        if (s.length() == 0 || s.length() < p.length()) {return res;}
        int[] letterCount = new int[26];
        int count = 0;
        int left = 0;
        int right = 0;
        for (Character c : p.toCharArray()) {
            letterCount[c - 'a'] += 1;
        }
        while (right < s.length()) {
            while (right < s.length() && right - left + 1 <= p.length()) {
                if (letterCount[s.charAt(right) - 'a'] > 0) {count += 1;}
                letterCount[s.charAt(right) - 'a'] -= 1;
                right++;
            }

            if (count == p.length()) {
                res.add(left);
            }

            if (letterCount[s.charAt(left) - 'a'] >= 0) {
                count -= 1;
            }

            letterCount[s.charAt(left) - 'a'] += 1;
            left++;
        }
        return res;
    }
}

[hengistchan]

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if(s.size()<p.size())
            return {};
        int l = 0, r = -1;
        vector<int> freq_s(26, 0), freq_p(26, 0), res;
        // 初始化代码值
        for( int i = 0 ; i < p.size() ; i++ ){
            freq_p[p[i] - 'a' ]++;
            freq_s[s[++r] - 'a' ]++;
        }
        if ( freq_s == freq_p )
            res.push_back( l );
        // 固定长度的滑动窗口
        while( r < s.size()-1 ){
            freq_s[s[++r] - 'a' ]++;
            freq_s[s[l++] - 'a' ]--;
            if ( freq_s == freq_p )
                res.push_back( l );
        }
        return res;
    }
};

[a244629128]

var findAnagrams = function (s, p) {
  const map = p.split('').reduce((map, e) => {
    if (map[e]) {
      map[e]++
    } else {
      map[e] = 1
    }
    return map
  }, {})
  const res = []
  function isInclude(a, map) {
    const arrA = a.split('')
    for (let i = 0; i < a.length; i++) {
      const e = a[i]
      if (map[e]) {
        map[e]--
      } else {
        return false
      }
    }
    return true
  }
  for (let i = 0; i <= s.length - p.length; i++) {
    if (map[s[i]] && isInclude(s.slice(i, i + p.length), Object.create(map))) {
      res.push(i)
    }
  }
  return res
};

[st2yang]

思路

• 滑动窗口
• 哈希表

代码

• python

  class Solution:
  def findAnagrams(self, s: str, p: str):
      l_s, l_p = len(s), len(p)
      if l_s < l_p:
          return []
  
      p_set = collections.defaultdict(int)
      for e in p:
          p_set[e] += 1
  
      res = []
      s_set = collections.defaultdict(int)
      for l in range(l_s - l_p + 1):
          r = l + l_p - 1
          if l == 0:
              for e in range(l, r + 1):
                  s_set[s[e]] += 1
          else:
              s_set[s[r]] += 1
              s_set[s[l - 1]] -= 1
              if s_set[s[l - 1]] == 0:
                  s_set.pop(s[l - 1])
  
          if p_set == s_set:
              res.append(l)
  
      return res

复杂度

• 时间: O(n)
• 空间: O(1)

[muimi]

思路

滑动窗口

代码

class Solution {
  public List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();
    if (s.length() < p.length()) return res;
    int[] key = new int[26];
    int[] curKey = new int[26];
    for (char ch : p.toCharArray()) key[ch -'a']++;
    for (int i = 0; i < p.length(); i++) curKey[s.charAt(i) -'a']++;
    if (Arrays.equals(curKey, key)) res.add(0);
    for (int i = p.length(); i < s.length(); i++) {
      curKey[s.charAt(i - p.length()) - 'a']--;
      curKey[s.charAt(i) - 'a']++;
      if (Arrays.equals(curKey, key)) res.add(i - p.length() + 1);
    }
    return res;
  }
}

复杂度

• 时间复杂度：O(N)
• 空间复杂度：O(1)

[ymkymk]

思路

滑动窗口

代码

``

public class Solution extends VersionControl {
   public List<Integer> findAnagrams(String s, String p) {
        int slen = s.length();
        int plen = p.length();
        List<Integer> list = new ArrayList<>();
        if (plen > slen || plen == 0 || slen == 0) {
            return list;
        }

        //一共只会有26个字母
        int[] sCnt = new int[26];
        int[] pCnt = new int[26];

        //统计p中每个字母出现的次数并存入相应位的数组
        for (int i = 0; i < plen; i++) {
            sCnt[s.charAt(i) - 'a']++;
            pCnt[p.charAt(i) - 'a']++;
        }

        //如果s中第一个p长度的字符串和p是异位词，存入0
        if (Arrays.equals(sCnt, pCnt)) {
            list.add(0);
        }

        //滑动窗口
        for (int i = plen; i < slen; i++) {
            sCnt[s.charAt(i - plen) - 'a']--;
            sCnt[s.charAt(i) - 'a']++;
            if (Arrays.equals(sCnt, pCnt)) {
                list.add(i -  plen + 1);
            }
        }

        return list;
    }
}

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

[hwpanda]

var findAnagrams = function(s, p) {

  if (p.length<1 || s.length<1)
      return [];

  let map = new Map();
  let charNeeded
  let count = p.length, right = 0, left = 0;
  let output = [];

  for (let char of p) {
      !map.has(char) ? map.set(char, 1) 
          : map.set(char, map.get(char)+1);
  }
  while (right<s.length) {
      if(map.get(s[right])>0) {
          count--;
      }
      //console.log("count: ", count, "right:", right)
      if(count === 0) output.push(left)
      if(map.has(s[right]))
          map.set(s[right], map.get(s[right])-1)
      //console.log(map,output,s[left], s[left+1], s[right], s[left+2])
      right ++
      if(right-left >= p.length) {
          if(map.get(s[left])>=0) {
              count++;
          }
          map.set(s[left], map.get(s[left])+1)
          left ++
      }

  }
  return output;
};

[biancaone]

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        counter = collections.Counter(p)
        valid_count = 0
        left = 0
        result = []

        for right in range(len(s)):
            if s[right] in counter:
                if counter[s[right]] > 0:
                    valirightd_count += 1
                counter[s[]] -= 1

            while valid_count == len(p):
                if right - left + 1 == len(p):
                    result.append(left)

                if s[left] in counter:
                    counter[s[left]] += 1
                    if counter[s[left]] > 0:
                        valid_count -= 1

                left += 1

        return result

[ai2095]

LC438. Find All Anagrams in a String

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

Topics

• slide window

思路

hashtable + slide window

代码 Python

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(s) < len(p):
            return []
        d_p = collections.Counter(p)
        d_s = defaultdict(int)
        result = []
        for i in range(len(s)):
            if i < len(p):
                d_s[s[i]] += 1
            else:
                d_s[s[i-len(p)]] -= 1
                d_s[s[i]] += 1
            is_anagram = True
            for e, cnt in d_p.items():
                if e not in d_s or cnt != d_s[e]:
                    is_anagram = False
                    break
            if is_anagram:
                result.append(i-len(p) + 1)

        return result

复杂度分析

时间复杂度： O(Ns + Np)
空间复杂度：O(1)

[laurallalala]

代码

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        # create a window
        win = [0]*26
        for c in p:
            win[ord(c)-ord('a')] += 1
        res = []
        for i in range(len(s)):
            # initialize win
            if i<len(p)-1:
                if s[i] in p:
                    win[ord(s[i])-ord('a')] -= 1
            else:
                if s[i] in p:
                    win[ord(s[i])-ord('a')] -= 1
                if sum(win) == 0 and min(win)>=0:
                    res.append(i-len(p)+1)
                if s[i-len(p)+1] in p:
                    win[ord(s[i-len(p)+1])-ord('a')] += 1
        return res

复杂度

• 时间复杂度：O(N)
• 空间复杂度：O(1)