【Day 45 】2023-03-30 - 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" 的字母异位词。

[JiangyanLiNEU]

• Sliding Window
• T = O(N) N = len(s)

• S = O(N) N = len(p)

  class Solution:
  def findAnagrams(self, s: str, p: str) -> List[int]:
      pChars = defaultdict(int)
      for char in p:
          pChars[char] += 1
      res, temp = [], []
  
      i = 0
      while i<len(s)+1:
          if len(temp) == len(p):
              [value, index] = temp.pop(0)
              res.append(index)
              pChars[value] += 1
  
          if i == len(s):
              return res
  
          if s[i] not in pChars.keys():
              while temp:
                  [value, index] = temp.pop(0)
                  if value in pChars.keys():
                      pChars[value] += 1
              i += 1
          else:
              if pChars[s[i]] > 0:
                  temp.append([s[i], i])
                  pChars[s[i]] -= 1
                  i += 1
              else:
                  [value, index] = temp.pop(0)
                  pChars[value] += 1

[bingzxy]

思路

滑动窗口 + 哈希表

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<> ();
        int sLen = s.length(), pLen = p.length();
        if (pLen > sLen) {
            return ans;
        }
        Map<Character, Integer> pCntMap = new HashMap<> ();
        for (char c : p.toCharArray()) {
            pCntMap.put(c, pCntMap.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = pLen - 1;
        Map<Character, Integer> slideMap = new HashMap<> ();
        for (int i = 0; i <= right; i++) {
            slideMap.put(s.charAt(i), slideMap.getOrDefault(s.charAt(i), 0) + 1);
        }

        do {
            if (valid(pCntMap, slideMap) && valid(slideMap, pCntMap)) {
                ans.add(left);
            }
            right++;
            if (right >= sLen) {
                return ans;
            }
            slideMap.put(s.charAt(right), slideMap.getOrDefault(s.charAt(right), 0) + 1);
            slideMap.put(s.charAt(left), slideMap.get(s.charAt(left)) - 1);
            left++;
        } while (right < sLen);

        return ans;
    }

    private boolean valid(Map<Character, Integer> targetMap, Map<Character, Integer> baseMap) {
        for (Character key : targetMap.keySet()) {
            if ((!baseMap.containsKey(key) && targetMap.get(key) > 0) ||
            (baseMap.containsKey(key) && !baseMap.get(key).equals(targetMap.get(key)))) {
                return false;
            }
        }
        return true;
    }
}

复杂度分析

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

[LIMBO42]

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;
        unordered_map<char, int> m;
        for(char ch : p) {
            m[ch]++;
        }
        int i = 0; int j = 0;
        unordered_map<char, int> c;
        for(; j < p.length(); ++j) {
            c[s[j]]++;
        }
        if(m == c) {
            ans.push_back(0);
        }
        for(; j < s.length(); ++j) {
            c[s[i]]--;
            if(c[s[i]] == 0) c.erase(s[i]);
            i++;
            c[s[j]]++;
            if(m == c) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

[kofzhang]

思路

滑动窗口 双指针，统计窗口中的每个字符个数，与p的统计相比较，一样就加入答案

复杂度

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

代码

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(s)<len(p):
            return []
        pos = 0
        l = len(p)
        c = Counter(p)
        for i in range(l):
            c[s[i]]-=1
        res = []
        diff = sum([abs(i) for i in c.values()])

        if diff==0:
            res.append(0)
        for i in s[l:]:
            if c[i]>0:
                diff -= 1
            else:
                diff += 1
            c[i]-=1
            if c[s[pos]] <0:
                diff -= 1
            else:
                diff += 1
            c[s[pos]]+=1
            pos += 1
            if diff==0:
                res.append(pos)
        return res

[wangzh0114]

class Solution {
public:
    vector<int> findAnagrams(string s, string t) {
        unordered_map<char, int> need, window;
        for (char c : t) need[c]++;
        int left = 0, right = 0;
        int valid = 0;
        vector<int> res; 
        while (right < s.size()) {
            char c = s[right];
            right++;
            if (need.count(c)) {
                window[c]++;
                if (window[c] == need[c]) 
                    valid++;
            }
            while (right - left >= t.size()) {
                if (valid == need.size())
                    res.push_back(left);
                char d = s[left];
                left++;
                if (need.count(d)) {
                    if (window[d] == need[d])
                        valid--;
                    window[d]--;
                }
            }
        }
        return res;
    }
};

• TC:O(N)
• SC:O(N)

[airwalkers]

class Solution {
     //   c b a e b a b a c d
    //   i
    //         j
    //[i,j)
    public List<Integer> findAnagrams(String s, String p) {
        int[] cnt = new int[26];
        for (char ch: p.toCharArray()) {
            cnt[ch - 'a']++;
        }

        int i = 0, j = 0, diff = p.length();
        char[] chars = s.toCharArray();
        List<Integer> ret = new ArrayList<>();
        while (j < chars.length) {
            // j
            cnt[chars[j] - 'a']--;

            if (cnt[chars[j] - 'a'] >= 0) {
                diff--;
            } else {
                diff++;
                while (cnt[chars[j] - 'a'] < 0) {
                    // i
                    if (cnt[chars[i] - 'a'] < 0) {
                        diff--;
                    } else {
                        diff++;
                    }
                    cnt[chars[i] - 'a']++;
                    i++;
                }
            }

            if (diff == 0) {
                ret.add(i);
            }
            j++;
        }
        return ret;
    }
}

[Meisgithub]

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int len = p.size();
        int n = s.size();
        if (n < len)
        {
            return {};
        }
        vector<int> pMap(26, 0);
        for (const char c : p)
        {
            ++pMap[c - 'a'];
        }
        vector<int> curMap(26, 0);
        for (int i = 0; i < len; ++i)
        {
            ++curMap[s[i] - 'a'];
        }
        vector<int> ans;
        int start = 0;
        if (isVal(curMap, pMap))
        {
            ans.push_back(start);
        }
        for (int i = len; i < n; ++i)
        {
            --curMap[s[start] - 'a'];
            ++curMap[s[i] - 'a'];
            ++start;
            if (isVal(curMap, pMap))
            {
                ans.push_back(start);
            }
        }
        return ans;
    }

    bool isVal(const vector<int> &curMap, const vector<int> & pMap)
    {
        for (int i = 0; i < 26; ++i)
        {
            if (curMap[i] != pMap[i])
            {
                return false;
            }
        }
        return true;
    }
};

[linlizzz]

思路

1. 滑动窗口依次遍历s的每个字符，并用字典记录

2. 滑入一个p中的字符则字典相应值的键+1，滑出一个p中的字符则字典相应值的键-1

3. 判断字典是否与p的原始字典相同，相同则记录该子串的起始位置

代码

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        cnt, p_dic = {}, {}
        for i in p:
            if not i in cnt:
                p_dic[i] = 1
                cnt[i] = 0
            else:
                p_dic[i] += 1

        ans = []
        for i in range(len(s)):
            if s[i] in p:
                cnt[s[i]] += 1
            if i-len(p) >= 0:
                if s[i-len(p)] in p:
                    cnt[s[i-len(p)]] -= 1
            if cnt == p_dic:
                ans.append(i-len(p)+1)
        return ans

复杂度分析

T(n) = O(len(s)+len(p))

S(n) = O(n), n为p中不重复的字符数

[Abby-xu]

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        count1 = collections.Counter(p)
        count2 = collections.Counter(s[:len(p)])
        i, j = 0, len(p)
        size = len(s)
        ans = []
        while j <= size:
            if count2 == count1:
                ans += i,
            if j < size:
                count2[s[j]] += 1
            count2[s[i]] -= 1
            if count2[s[i]]==0:
                del count2[s[i]]
            i += 1
            j += 1
        return ans

[NorthSeacoder]

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
const findAnagrams = (s, p) => {
    // 计算目标串 p 的长度以及记录每个字符出现次数的数组
    const len = p.length,
        pArr = new Array(26).fill(0),
        res = [];

    let count = len;

    // 对 p 中的每个字符在数组中进行计数
    // 这里我们将字符映射到 a~z 的索引上
    for (let i = 0; i < len; i++) {
        pArr[p.charCodeAt(i) - 'a'.charCodeAt()]++;
    }

    // 遍历字符串 s
    for (let i = 0; i < s.length; i++) {
        const char = s[i];

        // 对窗口内的字符进行计数，并更新 count 的值
        if (--pArr[char.charCodeAt() - 'a'.charCodeAt()] >= 0) {
            count--;
        }

        // 将窗口左端点向右移动一位，减少窗口大小
        // 同时更新 pArr 数组并更新 count 的值
        if (i >= len && ++pArr[s[i - len].charCodeAt() - 'a'.charCodeAt()] > 0) {
            count++;
        }

        // 如果 count 为 0，说明窗口内的字符与 p 中的字符完全匹配
        // 我们将窗口左端点加入结果集并继续遍历字符串 s
        if (count === 0) {
            res.push(i - len + 1);
        }
    }

    return res;
};

• TC:O(n)
• SC:O(1)

[FireHaoSky]

思路：

"""
滑动窗口与哈希表
"""

代码：python

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        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]) - 97] += 1
            s_cnt[ord(s[i]) - 97] += 1

        if s_cnt == p_cnt:
            res.append(0)

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

复杂度分析：

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

[chocolate-emperor]

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int len_p = p.length(),len_s = s.length();
        int letters_p[26]={0};
        int letters_s[26]={0};
        for(auto i:p){
            letters_p[i-'a'] +=1;
        }
        int l = 0;
        vector<int>res;
        for(int r = 0;r<len_s;r++){
            letters_s[s[r]-'a'] +=1;

            if(r-l+1>len_p){
                letters_s[s[l]-'a'] -=1;
                l+=1;
            }

            int flag = true;
            for(int i = 0; i<26;i++){
                if(letters_p[i] != letters_s[i])    flag = false;
            }
            if(flag)    res.emplace_back(l);
        }
        return res;
    }
};

[chanceyliu]

代码

function findAnagrams(s: string, p: string): number[] {
  const sLen = s.length,
    pLen = p.length;

  if (sLen < pLen) {
    return [];
  }

  const ans: number[] = [];
  const sCount = new Array(26).fill(0);
  const pCount = new Array(26).fill(0);
  for (let i = 0; i < pLen; ++i) {
    ++sCount[s[i].charCodeAt(0) - "a".charCodeAt(0)];
    ++pCount[p[i].charCodeAt(0) - "a".charCodeAt(0)];
  }

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

  for (let i = 0; i < sLen - pLen; ++i) {
    --sCount[s[i].charCodeAt(0) - "a".charCodeAt(0)];
    ++sCount[s[i + pLen].charCodeAt(0) - "a".charCodeAt(0)];

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

  return ans;
}

复杂度分析

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

[Fuku-L]

思路

滑动窗口。 1.处理特殊情况，如果 s 的长度小于 p 的长度可以直接返回。 2.使用两个数组分别统计s和滑动窗口中各个字母出现数目。

3. 第一次需要遍历s的长度，第二次循环从 0 到 s.length() - p.length() 即可。

代码

public class Q0438FindAllAnagramsInAString {
    public static void main(String[] args) {
        Solution solution = new Q0438FindAllAnagramsInAString().new Solution();
        List<Integer> anagrams = solution.findAnagrams("cbaebabacd", "abc");
        System.out.println(Arrays.toString(anagrams.toArray()));
    }
    class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> res = new ArrayList<>();
            if (s.length() < p.length()) {
                return res;
            }
            int pLen = p.length();
            int sLen = s.length();
            // 使用数组存储字符串 p 和 滑动窗口中每种字母得数量
            int[] pCnt = new int[26];
            int[] sCnt = new int[26];

            for (int i = 0; i < pLen; i++) {
                pCnt[p.charAt(i) - 'a']++;
                sCnt[s.charAt(i) - 'a']++;
            }
            if (Arrays.equals(pCnt, sCnt)) {
                res.add(0);
            }

            for (int i = 0; i < sLen - pLen; i++) {
                sCnt[s.charAt(i) - 'a']--;
                sCnt[s.charAt(i + pLen) - 'a']++;
                if (Arrays.equals(pCnt, sCnt)) {
                    res.add(i + 1);
                }
            }
            return res;
        }
    }
}

复杂度分析

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

[wwewwt]

思路

双指针移动，判断字符串是否相等

代码

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

        #构建字典
        base=dict()
        tmp =dict()
        for s_i in p:
            if s_i in base:
                base[s_i] += 1
            else:
                base[s_i] = 1
                tmp[s_i]  = 0

        #双指针
        for j in range(len(p)):
            if s[j] in tmp:
                tmp[s[j]] += 1

        i = 0
        result = []

        print(base)
        while j < len(s):
            if base == tmp:
                result.append(i)

            i += 1
            j += 1
            #更新tmp
            if j < len(s):
                if s[i - 1] in tmp:
                    tmp[s[i - 1]] -= 1

                if s[j] in tmp:
                    tmp[s[j]] += 1

        return result

复杂度

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

[snmyj]

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if(p.size()>s.size()) return {};
         vector<int> ret={};
         unordered_map<char,int> m,temp;
         for(auto x:p) m[x]++;
         temp=m;
         int cnt=0;
         for(int i=0;i<=s.size()-p.size();i++){
           if(temp.count(s[i])){
               cnt++;
               temp[s[i]]--;
               for(int j=i+1;j<i+p.size()+1;j++){
                   if(!temp.count(s[j])) break;
                   if(temp.count(s[j])&&temp[s[j]]!=0){
                       temp[s[j]]--;
                       cnt++;
                       continue;
                   }
                   if(temp[s[j]]==0) break;
               }
           }  
           if(cnt==p.size()) ret.push_back(i);
           temp=m;
           cnt=0;
         }
         return ret;
    }
};

[bookyue]

TC: O(n)
SC: O(1)

    public List<Integer> findAnagrams(String s, String p) {
        if (p.length() > s.length()) return List.of();

        int n = s.length();
        int m = p.length();

        int need = 0;
        int[] cnt = new int[26];
        for (int i = 0; i < m; i++) {
            if (cnt[p.charAt(i) - 'a']++ == 0) need++;
            if (cnt[s.charAt(i) - 'a']-- == 1) need--;
        }

        List<Integer> ans = new ArrayList<>();
        if (need == 0) ans.add(0);

        for (int i = m; i < n; i++) {
            if (cnt[s.charAt(i - m) - 'a']++ == 0) need++;
            if (cnt[s.charAt(i) - 'a']-- == 1) need--;

            if (need == 0) ans.add(i - m + 1);
        }

        return ans;
    }

[JasonQiu]

• Sliding window

  class Solution:
  def findAnagrams(self, s: str, p: str) -> List[int]:
      if len(s) < len(p):
          return []
      freq = defaultdict(int)
      result = []
      counter_s = Counter(s[:(len(p) - 1)])
      counter_p = Counter(p)
      pos = 0
      for pos in range(len(p) - 1, len(s)):
          counter_s[s[pos]] += 1
          if counter_s == counter_p:
              result.append(pos - len(p) + 1)
          counter_s[s[pos - len(p) + 1]] -= 1
          if counter_s[s[pos - len(p) + 1]] == 0:
              del counter_s[s[pos - len(p) + 1]]
      return result

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

[aoxiangw]

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(p) > len(s):
            return []
        sCount, pCount = {}, {}
        for i in range(len(p)):
            sCount[s[i]] = 1+ sCount.get(s[i], 0)
            pCount[p[i]] = 1 + pCount.get(p[i], 0)
        res = [0] if sCount == pCount else []

        l = 0
        for r in range(len(p), len(s)):
            sCount[s[r]] = 1 + sCount.get(s[r], 0)
            sCount[s[l]] -= 1
            if sCount[s[l]] == 0:
                sCount.pop(s[l])
            l += 1
            if sCount == pCount:
                res.append(l)
        return res

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

[Hughlin07]

class Solution {

public List<Integer> findAnagrams(String s, String p) {
    int sl = s.length(), pl = p.length();
    if(sl < pl){
        return new ArrayList();
    }

    int[] pCount = new int[26];
    int[] sCount = new int[26];

    for(char c : p.toCharArray()){
        pCount[(int) (c - 'a')] ++;
    }

    List<Integer> result = new ArrayList();

    for(int i = 0; i < sl; i++){
        sCount[(int) (s.charAt(i) - 'a')]++;
        if(i >= pl){
            sCount[(int)(s.charAt(i - pl) - 'a')] -- ; 
        }

        if(Arrays.equals(pCount, sCount)){
            result.add(i - pl + 1);
        }
    }

    return result;
}

}

[harperz24]

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

        p_count, s_count = [0] * 26, [0] * 26

        for ch in p:
            p_count[ord(ch) - ord('a')] += 1

        res = []
        # sliding window on the string s
        for i in range(len(s)):
            s_count[ord(s[i]) - ord('a')] += 1  # add
            if i >= len(p):
                s_count[ord(s[i - len(p)]) - ord('a')] -= 1  # remove
            # compare array in the sliding window with the reference array
            if p_count == s_count:
                res.append(i - len(p) + 1)

        return res

[GuitarYs]

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

    p_count, s_count = [0] * 26, [0] * 26

    for ch in p:
        p_count[ord(ch) - ord('a')] += 1

    res = []
    # sliding window on the string s
    for i in range(len(s)):
        s_count[ord(s[i]) - ord('a')] += 1  # add
        if i >= len(p):
            s_count[ord(s[i - len(p)]) - ord('a')] -= 1  # remove
        # compare array in the sliding window with the reference array
        if p_count == s_count:
            res.append(i - len(p) + 1)

    return res

[yingchehu]

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        l = r = 0
        p_cnt = collections.Counter(p) 
        seen = collections.defaultdict(int)
        ans = []

        while r <= len(s)-1:
            seen[s[r]] += 1

            while r-l+1 > len(p):
                seen[s[l]] -= 1
                if seen[s[l]] == 0:
                    del seen[s[l]]
                l += 1

            if r-l+1 == len(p) and p_cnt == seen:
                ans.append(l)
            r += 1
        return ans

[kangliqi1]

public List findAnagrams(String s, String p) { int sl = s.length(), pl = p.length(); if(sl < pl){ return new ArrayList(); }

int[] pCount = new int[26];
int[] sCount = new int[26];

for(char c : p.toCharArray()){
    pCount[(int) (c - 'a')] ++;
}

List<Integer> result = new ArrayList();

for(int i = 0; i < sl; i++){
    sCount[(int) (s.charAt(i) - 'a')]++;
    if(i >= pl){
        sCount[(int)(s.charAt(i - pl) - 'a')] -- ; 
    }

    if(Arrays.equals(pCount, sCount)){
        result.add(i - pl + 1);
    }
}
return result;

}

[Jetery]

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int m = s.size(), n = p.size();
        vector<int> ans;
        if (n > m) return ans;
        vector<int> ss(26, 0);
        vector<int> pp(26, 0);
        for (int i = 0; i < n; i++) {
            ss[s[i] - 'a']++;
            pp[p[i] - 'a']++;
        }
        if(ss == pp) ans.push_back(0);
        for (int i = n; i < m; i++) {
            ss[s[i - n] - 'a']--;
            ss[s[i] - 'a']++;
            if (ss == pp) ans.push_back(i - n + 1);
        }
        return ans;
    }
};

[jiujingxukong]

思路就是滑动窗口。

题目分析

首先题中说找到 s 中所有是 p 的字母异位词的字串，就这句话，就包含了如下两个重要信息： 找到符合要求的子串长度都是 p-->滑动窗口思路就出来了 何为字母异位词？也就是我们不关心 p 这个串的顺序，只关心字母是否出现以及出现的次数，这种问题解决方案一般有两种，一种是利用排序强制顺序，另一种就是用哈希表的方法。 针对如何存储 p 串这个问题，我们可以考虑用桶来装，这个桶既可以用 26 个元素的数组（作用其实也是哈希表）也可以用哈希表

错的地方

但我是个大憨批，该hashTable时用window,该window时用hashTable。还有滑动时left应该++，我写成--

JS代码

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
  const hashTable = new Map();
  const window = new Map();
  for (const i of p) {
    hashTable.set(i, (hashTable.get(i) || 0) + 1);
  }

  let left = 0,
    right = 0;
  const res = [];
  let valid = 0;

  while (right < s.length) {
    let i = s[right];
    right++;
    if (hashTable.has(i)) {
      window.set(i, (window.get(i) || 0) + 1);
      if (window.get(i) === hashTable.get(i)) {
        valid++;
      }
    }

    if (right - left >= p.length) {
      if (valid === hashTable.size) {
        res.push(left);
      }
      const d = s[left];
      left++;
      if (hashTable.has(d)) {
        if (hashTable.get(d) === window.get(d)) {
          valid--;
        }
        window.set(d, window.get(d) - 1);
      }
    }
  }
  return res;
};

复杂度分析

TC：O（n）,n为s字符串长度 SC：O（m）,m为p字符串长度

[RestlessBreeze]

code

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;
    }
};

[AstrKing]

public List findAnagrams(String s, String p) {

List<Integer> res = new LinkedList<>();
if (s == null || p == null || s.length() < p.length())
    return res;

int[] ch = new int[26];
//统计p串字符个数
for (char c : p.toCharArray())
    ch[c - 'a']++;
//把窗口扩成p串的长度
int start = 0, end = 0, rest = p.length();
for (; end < p.length(); end++) {
    char temp = s.charAt(end);
    ch[temp - 'a']--;
    if (ch[temp - 'a'] >= 0)
        rest--;
}

if (rest == 0)
    res.add(0);
//开始一步一步向右移动窗口。
while (end < s.length()) {
    //左边的拿出来一个并更新状态
    char temp = s.charAt(start);
    if (ch[temp - 'a'] >= 0)
        rest++;
    ch[temp - 'a']++;
    start++;
    //右边的拿进来一个并更新状态
    temp = s.charAt(end);
    ch[temp - 'a']--;
    if (ch[temp - 'a'] >= 0)
        rest--;
    end++;
    // 状态合法就存到结果集合
    if (rest == 0)
        res.add(start);
}

return res;

}

[Lydia61]

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

思路

滑动窗口

代码

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        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

        left = 0
        for right in range(n):
            cur_right = ord(s[right]) - ord('a')
            s_cnt[cur_right] += 1
            while s_cnt[cur_right] > p_cnt[cur_right]:
                cur_left = ord(s[left]) - ord('a')
                s_cnt[cur_left] -= 1
                left += 1
            if right - left + 1 == m:
                res.append(left)
        return res

复杂度分析

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

[lp1506947671]

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

复杂度分析

令 s 的长度为 n。

• 时间复杂度：O(n)
• 空间复杂度：虽然我们使用了数组（或者哈希表）存储计数信息，但是大小不会超过 26，因此空间复杂度为 O(1)

[duke-github]

思路

滑动窗口

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }

        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

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

            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}

[joemonkeylee]

思路

滑动窗口

代码

     public IList<int> FindAnagrams(string s, string p) {
        var res = new List<int>();
        if (s.Length < p.Length)
            return res;
        int[] charCnt = new int[26];
        for (int i = 0; i < p.Length; i++)
        {
            charCnt[s[i] - 'a']++;
            charCnt[p[i] - 'a']--;
        }
        var diff = 0;
        for (int i = 0; i < 26; i++)
        {
            diff += Math.Abs(charCnt[i]);
        }
        if (diff == 0)
        {
            res.Add(0);
        }
        for (int i = p.Length; i < s.Length; i++)
        {
            var enCharVal = s[i] - 'a';
            if (charCnt[enCharVal] < 0)
            {
                diff--;
            }
            else
            {
                diff++;
            }

            charCnt[enCharVal]++;
            var deCharVal = s[i - p.Length] - 'a';
            if (charCnt[deCharVal] > 0)
            {
                diff--;
            }
            else
            {
                diff++;
            }
            charCnt[deCharVal]--;
            if (diff == 0)
            {
                res.Add(i - p.Length + 1);
            }
        }
        return res;
    }

复杂度分析

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

[X1AOX1A]

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

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

[DrinkMorekaik]

var findAnagrams = function(s, p) {
  const len1 = s.length, len2 = p.length
  if (len1 < len2) return []

  const res = []
  const pMap = new Map()
  const sMap = new Map()
  let equal = 0

  for (const char of p) {
    pMap.set(char, (pMap.get(char) || 0) + 1)
  }

  let left = right = 0

  while (right < len1) {
    let strRight = s[right++]
    if (pMap.has(strRight)) {
      const count = (sMap.get(strRight) || 0) + 1
      sMap.set(strRight, count)
      count === pMap.get(strRight) && equal++
    }
    if (right - left === len2) {
      equal === pMap.size && res.push(left)

      let strLeft = s[left++]

      if (pMap.has(strLeft)) {
        let count = sMap.get(strLeft)
        if (pMap.get(strLeft) === count) equal--
        sMap.set(strLeft, --count)
      }
    }
  }
  return res
};

[huifeng248]

from collections import Counter, defaultdict

# sliding window with harsh map
# we keep increase the window size until P, and compare the two Counter
# when greater then P, we need to move left+1, and update the Counter_s and re-compare. 
# continue this process untill r reach the end.

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        counter_p = Counter(p)
        counter_s = Counter()
        i = 0
        left = 0
        res = []
        for i in range(len(s)):
            if i < len(p):
                counter_s[s[i]]+=1
            else:
                counter_s[s[left]]-= 1
                counter_s[s[i]]+=1
                if counter_s[s[left]] == 0:
                    del counter_s[s[left]]
                left += 1

            if counter_p == counter_s:
                res.append(left)
        return res

# time complexity: O(N) N is the length of s
# space complexity: O(1) becase of limited 26 letters