【Day 45 】2022-05-15 - 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" 的字母异位词。

[revisegoal]

滑动窗口

• 窗口大小：pLen
• 滑动策略：左减右增

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) {
            return new LinkedList<Integer>();
        }
        int[] sCnt = new int[26];
        int[] pCnt = new int[26];
        for (int i = 0; i < pLen; i++) {
            sCnt[s.charAt(i) - 'a']++;
            pCnt[p.charAt(i) - 'a']++;
        }
        List<Integer> res = new LinkedList<>();
        if (Arrays.equals(sCnt, pCnt)) {
            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(sCnt, pCnt)) {
                res.add(i + 1);
            }
        }
        return res;
    }
}

• time: O(sLen)
• space: O(Dict)

优化

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) {
            return new LinkedList<Integer>();
        }
        int[] cnt = new int[26];
        for (int i = 0; i < pLen; i++) {
            cnt[s.charAt(i) - 'a']++;
            cnt[p.charAt(i) - 'a']--;
        }
        int diff = 0;
        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] != 0) {
                diff++;
            }
        }
        List<Integer> res = new LinkedList<>();
        if (diff == 0) {
            res.add(0);
        }
        for (int i = 0; i < sLen - pLen; i++) {
            if (cnt[s.charAt(i) - 'a'] == 1) {
                diff--;
            }
            if (cnt[s.charAt(i) - 'a'] == 0) {
                diff++;
            }
            cnt[s.charAt(i) - 'a']--;
            if (cnt[s.charAt(i + pLen) - 'a'] == -1) {
                diff--;
            }
            if (cnt[s.charAt(i + pLen) - 'a'] == 0) {
                diff++;
            }
            cnt[s.charAt(i + pLen) - 'a']++;
            if (diff == 0) {
                res.add(i + 1);
            }
        }
        return res;
    }
}

• time: O(sLen)
• space: O(1)

[zhiyuanpeng]

from collections import defaultdict, Counter
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        w = len(p)
        n = len(s)
        if n < w:
            return None
        pd = Counter(p)
        wd = defaultdict(int)
        for c in s[:w]:
            wd[c] += 1
        ans = []
        for i in range(0, n-w+1):
            if wd == pd:
                ans.append(i)
            wd[s[i]] -= 1
            if wd[s[i]] == 0:
                del wd[s[i]]
            if i != n-w:
                wd[s[i+w]] += 1
        return ans

time O(Ns) space O(1)

[JiangWenqi]

Solution 1: 2 windows

class Solution {
private:
    bool check(int chars[], int target[]) {
        for (int i = 0; i < 26; i++) {
            if (chars[i] != target[i]) return false;
        }
        return true;
    }

public:
    vector<int> findAnagrams(string s, string p) {
        int target[26] = {0};

        for (char &c : p) target[c - 'a']++;

        vector<int> res;
        int n = p.size();
        int chars[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            chars[s[i] - 'a']++;
            if (i - n + 1 >= 0) {
                if (check(chars, target)) res.push_back(i + 1 - n);
                chars[s[i + 1 - n] - 'a']--;
            }
        }
        return res;
    }
};

Solution 2: 1 window

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> hash;
        for (auto &c : p) hash[c]++;

        vector<int> res;
        int total = hash.size(), seen = 0;
        for (int i = 0, j = 0; j < s.size(); j++) {
            if (--hash[s[j]] == 0) seen++;

            while (j - i + 1 > p.size()) {
                hash[s[i]]++;
                if (hash[s[i++]] == 1) seen--;
            }

            if (seen == total) res.push_back(i);
        }

        return res;
    }
};

[yanjyumoso]

• Slide window

  class Solution:
  def findAnagrams(self, s: str, p: str) -> List[int]:
      n = len(p)
      if len(s) < n:
          return []
      ans = []
      p_count = [0] * 26
      s_count =  [0] * 26
  
      for i in p:
          p_count[ord(i) - ord('a')] += 1
      for i in range(n):
          s_count[ord(s[i]) - ord('a')] += 1
      if s_count == p_count:
              ans.append(0)
      l, r = 1, n
      while r < len(s):
          s_count[ord(s[l-1]) - ord('a')] -= 1
          s_count[ord(s[r]) - ord('a')] += 1
          if s_count == p_count:
              ans.append(l)
          l += 1
          r += 1
      return ans

• Time: O(n)

• Space: O(1)

[KWDFW]

Day45

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

javascript #滑动窗口

思路

1、设置一个哈希表记录p

2、建立一个滑动窗口，每次根据窗口的变动，通过比较两个哈希表来判断是否满足异位词

3、返回结果数组

代码

var findAnagrams = function(s, p) {
  if(s.length<p.length) return []//处理特殊示例
  let ans=[]
  let sCount=new Array(26).fill(0)//动态哈希表记录当前的异位词
  let pCount=new Array(26).fill(0)//记录p
  for(let i in p){
    sCount[s[i].charCodeAt()-'a'.charCodeAt()]++//初始化滑动窗口
    pCount[p[i].charCodeAt()-'a'.charCodeAt()]++//将p记录在哈希表中
  }
  if(pCount.toString()===sCount.toString()) ans.push(0)//判断初始化的结果
  for(let i=0;i<s.length-p.length;i++){//遍历s
    sCount[s[i].charCodeAt()-'a'.charCodeAt()]--//窗口左侧收缩
    sCount[s[i+p.length].charCodeAt()-'a'.charCodeAt()]++//窗口右侧扩张
    if(pCount.toString()===sCount.toString()) ans.push(i+1)//如果是异位词，就存入索引
  }
  return ans
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

[miss1]

思路

滑动窗口，固定窗口长度

新建两个长度为26的数组，summary用于存储p中每个字母的个数，count用于存储窗口中的每个字母个数。每次移动窗口之后，比较summary和count是否完全相等，若相等，则当前窗口是一个解。

代码

var findAnagrams = function(s, p) {
  if (p.length > s.length) return [];
  let summary = new Array(26).fill(0);
  let count = new Array(26).fill(0);
  let start = 0, end = 0;
  let res = [];
  for (let i = 0; i < p.length; i++) summary[p[i].charCodeAt(0) - 97] += 1;
  while (end < p.length) {
    count[s[end].charCodeAt(0) - 97] +=1;
    end++;
  }
  if (count.toString() === summary.toString()) res.push(0);
  while (end < s.length) {
    count[s[end].charCodeAt(0) - 97] +=1;
    count[s[start].charCodeAt(0) - 97] -=1;
    end++;
    start++;
    if (count.toString() === summary.toString()) res.push(start);
  }
  return res;
};

复杂度分析

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

[MoonLee001]

思路

滑动窗口+hashmap

代码

var solve = function(s, p) {
  const n = s.length;
  const m = p.length;
  const map = new Map();
  for (let i = 0; i < m; i++) {
    map.set(p[i], (map.get(p[i]) || 0) + 1);
  }
  let window = {};
  let valid = 0;
  let left = 0, right = 0;
  let res = [];
  while (right < n) {
    const cur = s[right];
    right++;

    if (map.has(cur)) {
      window[cur] = window[cur] ? window[cur] + 1 : 1;
      if (window[cur] == map.get(cur)) {
        valid++;
      }
    }

    while(right - left >= p.length) {
      if (valid == map.size) {
        res.push(left);
      }

      if (map.has(s[left]) && window[s[left]] == map.get(s[left])) {
        valid--;
      }

      window[s[left]]--;
      left++;
    }
  }
  return res;
}

[BiN214]

public List<Integer> findAnagrams(String s, String p) {
        int[] chartP = new int[26];
        int sn = s.length(), pn = p.length();
        List<Integer> matchIndex = new ArrayList<>();

        for(char i:p.toCharArray())//p转为哈希
            chartP[i - 'a']++;

        for(int i = 0; i <= sn - pn; i++){
            int match = 1;
            int[] chartS = new int[26];
            for(int j = i; j < i + pn; j++){
                chartS[s.charAt(j) - 'a']++;
            }
            for(int ic = 0; ic < 26; ic++){
                if(chartP[ic] != chartS[ic]) {
                    match = 0;
                    break;
                }
            }
            if(match == 1) matchIndex.add(i);
        }
        return matchIndex;
    }

[houmk1212]

思路

固定窗口大小的滑动窗口+哈希表

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (s.length() < p.length()) {
            return new ArrayList<>();
        }
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < p.length(); i++) {
            char c = p.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int uncorrect = map.size();
        for (int i = 0; i < p.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
                if (map.get(c) == 0) {
                    uncorrect--;
                }
            }
        }
        List<Integer> res = new ArrayList<>();
        if (uncorrect == 0) {
            res.add(0);
        }

        for (int i = 1; i <= s.length() - p.length(); i++) {
            int j = i + p.length() - 1;
            // 离开的
            char c = s.charAt(i - 1);
            if (map.containsKey(c)) {
                if (map.get(c) == 0) {
                    uncorrect++;
                }
                map.put(c, map.get(c) + 1);
            }
            // 加入的
            c = s.charAt(j);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
                if (map.get(c) == 0) {
                    uncorrect--;
                }
            }

            if (uncorrect == 0) {
                res.add(i);
            }
        }
        return res;
    }
}

复杂度

领N是s的长度，M是p的长度

• 时间复杂度：O（N+M）
• 空间复杂度：O（M）

[zhulin1110]

题目地址(438. 找到字符串中所有字母异位词)

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

题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

 

示例 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" 的异位词。

 

提示:

1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母

前置知识

• 滑动窗口

代码

• 语言支持：JavaScript

JavaScript Code:

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
  const need = new Map();
  const window = new Map();
  for (const c of p) need[c] = (need[c] || 0) + 1;
  let left = 0;
  let right = 0;
  let valid = 0;
  let res = [];
  while (right < s.length) {
    let c = s[right];
    right++;
    if (need[c]) {
      window[c] = (window[c] || 0) + 1;
      if (window[c] == need[c]) {
        valid++;
      }
    }
    while (right - left >= p.length) {
      if (valid == Object.keys(need).length) {
        res.push(left);
      }
      let d = s[left];
      left++;
      if (need[d]) {
        if (window[d] == need[d]) {
          valid--;
        }
        window[d]--;
      }
    }
  }
  return res;
};

复杂度分析

令 n 为字符串长度。

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

[Geek-LX]

5.15

思路：滑动窗口

代码：

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)

[Yongxi-Zhou]

思路

hashmap，进出算

代码

    class Solution:
        def findAnagrams(self, s: str, p: str) -> List[int]:
            p_counter = Counter(p)
            s_counter = collections.defaultdict(int)
            res = []
            left = 0

            for i in range(len(s)):
                # 右窗口进入
                s_counter[s[i]] += 1

                # 左窗口退出
                if i - left + 1 > len(p):
                    char = s[left]
                    left += 1
                    s_counter[char] -= 1
                    if s_counter[char] == 0:
                        s_counter.pop(char)

                # 算符合条件的结果
                if p_counter == s_counter:
                    res.append(left)
            return res

复杂度

time O(N) space O(N)

[caterpillar-0]

思路

小写字母，用数组来做哈希表，使用differ变量来减少空间复杂度

代码

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int>res;
        //滑动窗口
        int size_s=s.size();
        int size_p=p.size();
        if(size_p>size_s){
            return res;
        }
        //优化，使用一个数组+differ变量来判断，减少空间复杂度
        vector<int>count(26,0);
        for(int i=0;i<size_p;i++){
            count[p[i]-'a']--;
            count[s[i]-'a']++;
        }
        //统计differ变量
        int differ=0;
        for(int num:count){
            if(num!=0){
                differ++;
            }
        }
        if(differ==0){
            res.push_back(0);
        }
        //滑动窗口
        for(int i=0;i<size_s-size_p;i++){
            //处理左边界i,是要减的
            if(count[s[i]-'a']==1){
                differ--;
            }
            else if(count[s[i]-'a']==0){
                differ++;
            }
            count[s[i]-'a']--;
            //处理右边界i+size_p;
            if(count[s[i+size_p]-'a']==-1){
                differ--;
            }
            else if(count[s[i+size_p]-'a']==0){
                differ++;
            }
            count[s[i+size_p]-'a']++;
            //判断
            if(differ==0){
                res.push_back(i+1);
            }
        }       
      return res;
    }
};

复杂度分析

• 时间复杂度：o(n)
• 空间复杂度：o(26),

[currybeefer]

思路：这题就是滑动窗口，没别的

   vector<int> findAnagrams(string s, string p) 
    {
        vector<int> res;
        int left=0, right=0;
        int valid=0;
        unordered_map<char,int> need;
        unordered_map<char,int> window;
        for(char son: p)
            need[son]++;

        while(right<s.size())
        {
            char c=s[right];
            right++;
            if(need.count(c))
            {
                window[c]++;
                if(need[c]==window[c])
                   valid++;
            }
            while(right-left>=p.size())
            {
                if(valid==need.size())
                    res.push_back(left);
                char d=s[left];
                left++;
                if(need.count(d))
                {
                    if(need[d]==window[d])
                        valid--;

                    window[d]--;
                }
            }
        }
        return res;
    }

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

[Jessie725]

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

    int[] hash = new int[256];
    for (char c : p.toCharArray()) {
        hash[c]++;
    }

    int left = 0;
    int right = 0;
    int count = p.length();

    while (right < s.length()) {
        if (hash[s.charAt(right)] >= 1) {
            count--;
        }
        hash[s.charAt(right)]--;
        right++;

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

        if (right - left == p.length()) {
            if (hash[s.charAt(left)] >= 0) {
                count++;
            }
            hash[s.charAt(left)]++;
            left++;
        }

    }
    return res;
}

}

[HuiWang1020]

Idea

1. calculate the frequency of every letter by using a 26 sized array
2. use a fixed size sliding window.
3. check the frequency of char in the window

Code

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

        int[] count = new int[26];
        for (int i = 0; i < p.length(); i++) {
            count[p.charAt(i) - 'a']++;
        }

        int need = p.length();
        for (int i = 0; i < p.length(); i++) {
            count[s.charAt(i) - 'a']--;
            //still need this char
            if (count[s.charAt(i) - 'a'] >= 0) need--;
            if (need == 0) res.add(0);
        }

        for (int i = p.length(); i < s.length(); i++) {
            char right = s.charAt(i);
            char left = s.charAt(i - p.length());
            count[right - 'a']--;
            if (count[right - 'a'] >= 0) need--;
            if (count[left - 'a'] >= 0) need++;
            count[left - 'a']++;
            left++;
            if (need == 0) res.add(i - p.length() + 1);
        }
        return res;
    }
}

Complexity

time=o(n) space=o(1)

[Ellie-Wu05]

思路 滑动窗口

学习官方题解

代码

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

复杂度

时间On 空间O1

[ShawYuan97]

思路

滑动窗口的使用

关键点

• 如何比较两个字符串的组成相同
• 如何维护滑动窗口

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        """
        找到字符串中所有字母异位词（指那些由相同字母重排列形成的字符串）

        思路：
        如何使用滑动窗口 
        如何比较两个字符串内容相等
        """
        s_len, p_len = len(s), len(p)

        # 第一种情况 在长度上p>s 直接返回空
        if s_len < p_len:
            return []
        # 维护一个字母差异表
        ans = []
        count = [0] * 26
        # 遍历字符串p 出现在字符串s中的字母 个数加一；
        # 出现在字符串p中的字母 个数减一
        for i in range(p_len):
            count[ord(s[i]) - 97] += 1
            count[ord(p[i]) - 97] -= 1
        # 对differ中 不为0的地方进行计数
        differ = [c != 0 for c in count].count(True)
        # 如果differ为零 说明找到一个子串
        if differ == 0:
            ans.append(0)

        # 前面已经比较了p_len个字符 因为只需要再次移动s_len - p_len
        for i in range(s_len - p_len):
            # 考虑滑动窗口左边界
            # 相当于将滑动窗口向右移动一格
            # 如果该字符在count中数量为1 说明s中子串比p字符串多一个s[i]，如果移动后，differ就减一
            if count[ord(s[i]) - 97] == 1:  # 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
                differ -= 1
            # 反之，differ就加一
            elif count[ord(s[i]) - 97] == 0:  # 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
                differ += 1
            # 该操作说明滑动窗口向右移动了一格
            count[ord(s[i]) - 97] -= 1

            # 考虑滑动窗口右边界
            if count[ord(s[i + p_len]) - 97] == -1:  # 窗口中字母 s[i+p_len] 的数量与字符串 p 中的数量从不同变得相同
                differ -= 1
            elif count[ord(s[i + p_len]) - 97] == 0:  # 窗口中字母 s[i+p_len] 的数量与字符串 p 中的数量从相同变得不同
                differ += 1
            count[ord(s[i + p_len]) - 97] += 1
            if differ == 0:
                ans.append(i + 1)
        return ans

复杂度分析

时间复杂度：O(n+m+Σ)，其中 nn 为字符串 s 的长度，m 为字符串 pp 的长度，其中Σ 为所有可能的字符数。我们需要 O(m) 来统计字符串 p 中每种字母的数量；需要 O(m) 来初始化滑动窗口；需要 O(Σ) 来初始化 differ；需要 O(n-m) 来滑动窗口并判断窗口内每种字母的数量是否与字符串 p 中每种字母的数量相同，每次判断需要 O(1) 。因为 s 和 p 仅包含小写字母，所以 Σ=26。

空间复杂度：O(Σ)。用于存储滑动窗口和字符串 p 中每种字母数量的差。

参考链接

https://leetcode.cn/problems/find-all-anagrams-in-a-string/solution/zhao-dao-zi-fu-chuan-zhong-suo-you-zi-mu-xzin/

[zzz607]

思路

在字符串s中，取一段与p长度相同的子串，判断此子串中各字母的数量与模式串p中的各字符的数量是否相同

代码

func findAnagrams(s string, p string) []int {
    var ret []int
    target := make([]int, 26)
    source := make([]int, 26)

    for _, c := range p {
        target[c - 'a']++
    }

    begin := 0
    cur := begin
    end := len(p) - 1
    for cur <= end && cur < len(s) && end < len(s) {
        idx := s[cur] - 'a'
        if target[idx] == 0 {
            // 字母在s中，不在p中，左、右边界同时滑动，且左边界滑到cur的下一位
            cur++
            begin = cur
            end = cur + len(p) - 1
            for i := 0; i < 26; i++ {
                source[i] = 0
            }
            continue
        }

        source[idx]++
        if source[idx] > target[idx] {
            // 字母在s和p中，但是在s中的数量多于在p中的数量，左、右边界同时滑动
            // 且左边界滑动到第一个s[cur]的下一位
            for i := begin; i < cur; i++ {
                idx := s[i] - 'a'
                source[idx]--
                if s[i] == s[cur] {
                    begin = i + 1
                    end = begin + len(p) - 1
                    cur++
                    break
                }
            }
            continue
        }

        if cur == end {
            // 找到一个？
            ret = append(ret, begin)
            source[s[begin] - 'a']--
            begin++
            end++
        }

        cur++
    }

    return ret
}

复杂度分析

• 时间复杂度：？？
• 空间复杂度：O(1)，固定为二个长度为26的整数数组

[carterrr]

class Solution { public List findAnagrams(String s, String p) { int sLen = s.length(), window = p.length(), r = 0, l = 0; int[] pc = new int[26]; int[] sc = new int[26]; char[] charsP = p.toCharArray(); char[] charsS = s.toCharArray(); List res = new ArrayList<>(); for (char c : charsP) { pc[c - 'a'] ++; } while (r < sLen) { int rChar = charsS[r] - 'a'; sc[rChar]++; while (sc[rChar] > pc[rChar]) { sc[charsS[l++] - 'a'] --; // sc中 左边界对应的字符数量减一 最多减少到 r = l } if(r - l + 1== window) { // l到r刚好和p长度相等 而且窗口中对应字符数量和p都相等 那么就是异构词 res.add(l); } r ++; } return res; } }

[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

[xiayuhui231]

题目

找到字符串中所有字母异位词 https://leetcode.cn/problems/find-all-anagrams-in-a-string/

思路

滑动窗口

代码

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()) {
            // 当窗口符合条件时，把起始索引加入 res
            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;
    }
};

复杂度

时间复杂度:O(N) 空间复杂度:O(1)

[xingchen77]

思路

滑动窗口 + Counter

代码

    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)

[rzhao010]

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> res = new ArrayList<>();
        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)) {
            res.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)) {
                res.add(i + 1);
            }
        }
        return res;
    }
}

[LQyt2012]

思路

滑动指针

代码

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

        if s_len < p_len:
            return []

        ans = []
        s_count = [0] * 26
        p_count = [0] * 26
        for i in range(p_len):
            s_count[ord(s[i]) - 97] += 1
            p_count[ord(p[i]) - 97] += 1

        if s_count == p_count:
            ans.append(0)

        for i in range(s_len - p_len):
            s_count[ord(s[i]) - 97] -= 1
            s_count[ord(s[i + p_len]) - 97] += 1

            if s_count == p_count:
                ans.append(i + 1)

        return ans

复杂度分析

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

[L-SUI]

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, t) {
  // 需要的
  let need = {};
  // 窗口中的字符
  let window = {};
  for (let a of t) {
    // 统计需要的字符
    need[a] = (need[a] || 0) + 1;
  }
  // 左右指针
  let left = 0,
    right = 0;
  let valid = 0;
  let res = [];
  while (right < s.length) {
    // 即将移入窗口的字符
    let c = s[right];
    // 右移窗口
    right++;
    if (need[c]) {
      // 当前字符在需要的字符中，则更新当前窗口统计
      window[c] = (window[c] || 0) + 1;
      if (window[c] == need[c]) {
        // 当前窗口和需要的字符匹配时，验证数量增加1
        valid++;
      }
    }
    while (right - left >= t.length) {
      if (valid == Object.keys(need).length) {
        res.push(left);
      }
      let d = s[left];
      left++;
      if (need[d]) {
        if (window[d] == need[d]) {
          valid--;
        }
        window[d]--;
      }
    }
  }
  return res;
};

[JasonHe-WQ]

代码：

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ls = len(s)
        lp = len(p)
        dicP = collections.Counter(p)
        ans = []
        for i in range(ls):
            temp = s[i:i + lp]
            dicS = collections.Counter(temp)
            if dicP == dicS:
                ans.append(i)
        return ans

思路： 采用counter，记录各个元素出现次数，再比较

[mo660]

思路

滑动窗口，哈希存储每个元素出现的个数，最后比较

代码

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;
        int len = p.length();
        map<char,int>mp;
        map<char,int>mpcom;
        for (int i= 0;i<p.length();i++){
            mp[p[i]]++;
            mpcom[p[i]]=0;
        }
        for (int i= 0;i<p.length();i++){
            if(mp.find(s[i])!=mp.end()) mpcom[s[i]]++;
        }
        if (mpcom == mp)ans.push_back(0);
        for (int i = len;i<s.length();i++){
            if(mp.find(s[i])!=mp.end()) mpcom[s[i]]++;
            if(mp.find(s[i-len])!=mp.end()) mpcom[s[i-len]]--;
            if (mpcom == mp)
                ans.push_back(i-len+1);
        }
        return ans;
    }
};

[MichaelXi3]

Idea

• Sliding Window

• 维护一个符合条件的滑动窗口

  Code

  class Solution {
  public List<Integer> findAnagrams(String s, String p) {
      // List that stores results
      List<Integer> res = new ArrayList<>();
      if (p.length() > s.length()) { return res; } // Base case
  
      // Use Array to store target string info: Char & Frequency
      int[] target = new int[26];
      for (int i=0; i<p.length(); i++) {
          target[p.charAt(i) - 'a']++;
      }
  
      // Use Array to store string s info: Char & Frequency
      // Sliding window begins
      int[] window = new int[26];
      for (int i=0; i<p.length(); i++) {
          window[s.charAt(i) - 'a']++;
      }
  
      // Compare and see whether the first set of comparsion is valid
      if (isEqual(window, target)) {res.add(0);}
  
      // Compare the rest of string s, sliding window begin to slide
      int i = 0, sLength = s.length(), pLength = p.length();
      while (i < sLength - pLength) {
          window[s.charAt(i) - 'a']--;
          window[s.charAt(i + pLength) - 'a']++;
          i++;
          if (isEqual(window, target)) {res.add(i);}
      }
      return res;
  }
  
  private boolean isEqual(int[] arr, int[] target) {
      for (int i=0; i<target.length; i++) {
          if (arr[i] != target[i]) {
              return false;
          }
      }
      return true;
  }
  }

  Complexity

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

[testeducative]

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> count(26);
        for (int i = 0; i < pLen; ++i) {
            ++count[s[i] - 'a'];
            --count[p[i] - 'a'];
        }

        int differ = 0;
        for (int j = 0; j < 26; ++j) {
            if (count[j] != 0) {
                ++differ;
            }
        }

        if (differ == 0) {
            ans.emplace_back(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            if (count[s[i] - 'a'] == 1) {  
                --differ;
            } else if (count[s[i] - 'a'] == 0) {  
                ++differ;
            }
            --count[s[i] - 'a'];

            if (count[s[i + pLen] - 'a'] == -1) {  
                --differ;
            } else if (count[s[i + pLen] - 'a'] == 0) {  
                ++differ;
            }
            ++count[s[i + pLen] - 'a'];

            if (differ == 0) {
                ans.emplace_back(i + 1);
            }
        }

        return ans;
    }
};

[tensorstart]

思路

哈希+滑动窗口

代码

var findAnagrams = function(s, p) {
    if (s.length<p.length) return [];
    let map_p=new Map();
    for (let i = 0; i < p.length; i++) {
        if (map_p.has(p[i])){
            let value=map_p.get(p[i]);
            map_p.set(p[i],++value);
        }else map_p.set(p[i],1);
    }
    let l=0,r=p.length-1;
    let map_cur=new Map();
    for (let i = 0; i <=r; i++) {
        if (map_cur.has(s[i])){
            let value=map_cur.get(s[i]);
            map_cur.set(s[i],++value);
        }else map_cur.set(s[i],1);
    }
    let res=[];
    while (r<s.length){
        if (containsstr(map_p,map_cur)) res.push(l);
        let value=map_cur.get(s[l]);
        if (--value===0)map_cur.delete(s[l]);
        else map_cur.set(s[l],value);
        l++;r++;
        if (r===s.length)break;
        if (map_cur.has(s[r])){
            let value=map_cur.get(s[r]);
            map_cur.set(s[r],++value);
        }else map_cur.set(s[r],1);

    }
    return res;

};
var containsstr=function (map_p,map_s){
    if (map_s.size!==map_p.size) return false;
    else {
        for(let entry of map_p){
            if (map_s.has(entry[0])&&map_s.get(entry[0])===entry[1])
                continue;
            else return false;
        }
        return true;
    }
}

复杂度分析 时间O(n) 空间O(n)

[wychmod]

思路

滑动窗口+哈希表

代码

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(s) < len(p):
            return []
        dic = {}
        ans = []
        for ch in p:
            dic[ch] = dic.get(ch, 0)+1
        for i in range(len(p)):
            if s[i] in dic:
                dic[s[i]] = dic[s[i]]-1
        def judge(arr):
            for i in arr:
                if i != 0:
                    return False
            return True
        if judge(dic.values()):
            ans.append(0)
        l, r = 0, len(p)
        while r<len(s):
            if s[l] in dic:
                dic[s[l]] = dic[s[l]]+1
            if s[r] in dic:
                dic[s[r]] = dic[s[r]]-1
            if judge(dic.values()):
                ans.append(l+1)
            l += 1
            r += 1
        return ans

复杂度

时间复杂度：On*m 空间复杂度：On

[freedom0123]

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        //双指针算法
        List<Integer> res = new ArrayList<>();
        int []hash = new int[26];
        char[] sChar = s.toCharArray();
        char[] pChar = p.toCharArray();
        //统计当前子串中每一位字母出现的个数
        for(char c:p.toCharArray()){
            hash[c-'a']++;
        }
        int target  = 0;
        for(int i =  0;i <26;i++){
            if(hash[i]!=0){
                target++;
            }
        }
        for(int i  = 0 ,j = 0,satisfy  =0 ;i<s.length();i++){
            if(--hash[sChar[i]-'a'] == 0){
                satisfy++;
            }
            while(i-j+1>p.length()){
                if(hash[sChar[j]-'a']== 0){
                    satisfy--;
                }
                hash[sChar[j++]-'a']++;

            }
            if(satisfy == target){
                res.add(j);
            }

        }
        return res;

    }
}

[ShirAdaOne]

思路

438. 找到字符串中所有字母异位词 https://leetcode.cn/problems/find-all-anagrams-in-a-string/

代码

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

[zjsuper]

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        lens = len(p)
        ans = []
        c2 = Counter(p)
        c1 = Counter(s[0:0+lens])
        if c1 == c2:
            ans.append(0)
        for i in range(1,len(s)-lens+1):
            left = s[i-1]
            right = s[i+lens-1]
            if left in c1:
                c1[left] -=1
                if c1[left] ==0:
                    del c1[left]
            if right in c1:
                c1[right] +=1
            else:
                c1[right] =1
            if c1 == c2:
                ans.append(i)

        return ans

[AConcert]

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int len1 = s.length();
        int len2 = p.length();
        if(len1 < len2) return new ArrayList<>();
        int left = 0, right = len2;
        int[] a = new int[26];
        int[] b = new int[26];
        ArrayList<Integer> c = new ArrayList<>();
        for(int i = 0; i < len2; i++){
            a[s.charAt(i) - 'a']++;
            b[p.charAt(i) - 'a']++;
        }
        if(Arrays.equals(a, b)) c.add(0);
        while(right < len1){
            a[s.charAt(right) - 'a']++;
            a[s.charAt(left) - 'a']--;
            if(Arrays.equals(a, b)) c.add(left + 1);
            right++;
            left++;
        }
        return c;
    }
}

[hyh331]

Day45 思路

在字符串S中构造一个长度与p相同的滑动窗口，并在滑动中维护窗口中没中字母的数量，当窗口中每种字母数量==p中每种字母数量时，则说明当前窗口为字符串p的异位词

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> need, winow;
        //将需要做对比的p全部放入need容器内，记录每个字符和个数
        for(char c : p) need[c]++;
        int left = 0, right = 0;
        //valid变量表示窗口中满足 need 条件的字符个数
        int valid = 0;
        vector<int> res;
        //滑动窗口
        while(right < s.size()){
            //c为即将从右端进入窗口的字符
            char c=s[right];
            right++;
            //进行窗口内数据的更新,count 找到返回1，未找到返回0,
            if(need.count(c)){
                //找到则将此字母加入到窗口中
                winow[c]++;
                //判断window和need中的c个数是否相同
                if(winow[c]==need[c]) valid++;
            }
            //判断左端窗口什么时候收缩
            while(right-left >= p.size()){
                //当窗口符合条件时，把起始索引加入res
                if(valid == need.size()) res.push_back(left);
                char d=s[left];
                left++;
                //进行窗口内数据的更新
                if(need.count(d)){
                    if(winow[d] == need[d]) valid--;
                    winow[d]--;
                }
            }
        }
        return res;
    }
};

复杂度分析

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

[Orangejuz]

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        n = len(p)
        if len(s) < n:
            return []
        ans = []
        p_count = [0] * 26
        s_count =  [0] * 26

        for i in p:
            p_count[ord(i) - ord('a')] += 1
        for i in range(n):
            s_count[ord(s[i]) - ord('a')] += 1
        if s_count == p_count:
                ans.append(0)
        l, r = 1, n
        while r < len(s):
            s_count[ord(s[l-1]) - ord('a')] -= 1
            s_count[ord(s[r]) - ord('a')] += 1
            if s_count == p_count:
                ans.append(l)
            l += 1
            r += 1
        return ans

[lizimu0709]

思路 滑动窗口

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

        if (m < n) {
            // 如果s没p长，直接返回空列表
            return ans;
        }

        int[] sCnt = new int[26];
        int[] pCnt = new int[26];

        for (int i = 0; i < n; i++) {
            sCnt[s.charAt(i) - 'a']++;
            pCnt[p.charAt(i) - 'a']++;
        }

        if (Arrays.equals(sCnt, pCnt)) {
            // 初始窗口就相等
            ans.add(0);
        }

        for (int i = 0; i < m - n; i++) {
            // 窗口右移
            sCnt[s.charAt(i) - 'a']--;
            sCnt[s.charAt(i + n) - 'a']++;

            if (Arrays.equals(sCnt, pCnt)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}

时间复杂度：O(m + (m - n) * C) 空间复杂度：O(C)

[maggiexie00]

def findAnagrams(self, s: str, p: str) -> List[int]:
    s_len, p_len = len(s), len(p)

    if s_len < p_len:
        return []

    ans = []
    count = [0] * 26
    for i in range(p_len):
        count[ord(s[i]) - 97] += 1
        count[ord(p[i]) - 97] -= 1

    differ = [c != 0 for c in count].count(True)

    if differ == 0:
        ans.append(0)

    for i in range(s_len - p_len):
        if count[ord(s[i]) - 97] == 1:  
            differ -= 1
        elif count[ord(s[i]) - 97] == 0:  
            differ += 1
        count[ord(s[i]) - 97] -= 1

        if count[ord(s[i + p_len]) - 97] == -1:  
            differ -= 1
        elif count[ord(s[i + p_len]) - 97] == 0:  
            differ += 1
        count[ord(s[i + p_len]) - 97] += 1

        if differ == 0:
            ans.append(i + 1)

    return ans

[XXjo]

思路

1、滑动窗口
2、通过将数组转化为字符串，比较字符串是否相等，来判断是否是异位词

代码

    let res = [];
    let target = new Array(26).fill(0);
    for(let c of p){
        target[c.charCodeAt() - 'a'.charCodeAt()] += 1;
    }

    let left = 0;
    let right = 0;
    let window = new Array(26).fill(0);
    while(right < s.length){
        window[s[right].charCodeAt() - 'a'.charCodeAt()] += 1;
        if(right - left + 1 == p.length){
            if(JSON.stringify(window) === JSON.stringify(target)){
                res.push(left);
            }
            window[s[left].charCodeAt() - 'a'.charCodeAt()] -= 1;
            left += 1;
        }
        right += 1;
    }
    return res;

复杂度分析

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

[taojin1992]

/*
map + sliding window

Time: O(s.length() + p.length())
space: O(uniq letter num in p) = O(26) = O(1)
*/

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> answer = new ArrayList<>();
        Map<Character, Integer> charFreqMap = new HashMap<>();
        // record p, letter-freq map
        for (int i = 0; i < p.length(); i++) {
            charFreqMap.put(p.charAt(i), charFreqMap.getOrDefault(p.charAt(i), 0) + 1);
        }
        int counter = charFreqMap.size();// unique letter num in p
        // sliding window
        int l = 0, r = 0;
        while (r < s.length()) {
            char rightChar = s.charAt(r);

            if (charFreqMap.containsKey(rightChar)) {
                // update map
                charFreqMap.put(rightChar, charFreqMap.get(rightChar) - 1);
                if (charFreqMap.get(rightChar) == 0) {
                    counter--;
                }
            }
            r++;
            while (counter == 0) {
                char leftChar = s.charAt(l);

                if (charFreqMap.containsKey(leftChar)) {
                    // update map
                    charFreqMap.put(leftChar, charFreqMap.get(leftChar) + 1);
                    if (charFreqMap.get(leftChar) > 0) {
                        counter++;
                    }
                }

                if (r - l == p.length()) {
                    answer.add(l);
                }
                l++;
            }

        }
        return answer;
    }
}

[houyanlu]

思路

滑动窗口中每种字母的数量与字符串 p 中每种字母的数量相同时 满足条件 每次出的字符减， 进入的字符增， 加减完之后进行比较和p中的数量。

代码

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

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

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

        for (int i = p.size(); i < s.size(); i++) {
            ++sCount[s[i] - 'a'];
            --sCount[s[i - p.size()] - 'a']; 

            if (sCount == pCount) {
                ans.push_back(i - p.size() + 1);
            }           
        }

        return ans;
    }
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1) 两个计数的vector的空间， 52个int

[xil324]

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        countLetter = collections.defaultdict(int); 
        needLetter = collections.defaultdict(int); 
        for letter in p:
            countLetter[letter] += 1; 
        valid = 0; 
        left = 0; 
        right = 0; 
        res = []; 
        while right < len(s): 
            curr = s[right]; 
            right += 1; 
            if curr in countLetter: 
                needLetter[curr] += 1;
                if needLetter[curr] == countLetter[curr]:
                    valid += 1; 
            while right -left >= len(p): 
                if valid == len(countLetter):
                     res.append(left); 
                if s[left] in countLetter:
                    if needLetter[s[left]] == countLetter[s[left]]:
                        valid -=1;
                    needLetter[s[left]] -=1; 
                left += 1; 
        return res; 

time complexity: O(n)

[gitbingsun]

题目地址(438. 找到字符串中所有字母异位词)

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

题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 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" 的异位词。

 

提示:

1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母

关键点

滑动窗口。用一个固定大小的数组存字母出现的次数。

class Solution { public: vector findAnagrams(string s, string p) { int pLen = p.length(); int sLen = s.length(); vector pVec(26,0); vector sVec(26,0); for (auto i : p) { ++pVec[i-'a']; }

    vector<int> res;
    for (int i = 0; i < sLen; i++) {
       ++sVec[s.at(i)-'a'];
       if (i>=pLen) {
           --sVec[s.at(i-pLen)-'a'];
       }
       if (sVec == pVec) res.push_back(i-pLen+1);
    }
    return res;
}

};

**复杂度分析**

令 n 为数组长度。

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

[hyh331]

Day45 思路

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> need, window;
        for(char c : t) need[c]++;
        int left = 0, right = 0;
        //valid变量表示窗口中满足 need 条件的字符个数,若valid和need.size大小相同，则说明窗口完全包含了串t
        int valid = 0;
        //记录最小覆盖子串的起始索引及长度
        int start=0,len=INT_MAX;
        while(right < s.size()){
            //c为将要进入窗口的字符
            char c=s[right];
            right++;
            //窗口内数据更新
            if(need.count(c)){
                window[c]++;
                //判断win和need中c的个数是否相同
                if(window[c] == need[c]) valid++;
            }
            //左窗口移动条件！！！！！
            while(valid == need.size()){
                //在这里更新最小覆盖子串！！！！！！！！！！！
                if(right - left <len){
                    start =left;
                    len= right - left;
                }
                char d=s[left];
                left++;
                //窗口内数据更新
                if(need.count(d)){
                    if(window[d] == need[d]) valid--;
                    window[d]--;
                }
            }
        }
        //substr为截取字符串,从start开始，长度为len
        return len == INT_MAX? "" : s.substr(start,len);

    }
};

复杂度分析

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

[zhishinaigai]

思路

滑动窗口

代码

vector<int> findAnagrams(string s, string p) {
        int slen=s.size();
        int plen=p.size();
        if(slen<plen) return vector <int> {};
        vector<int> ans;
        vector<int> scount(26,0);
        vector<int> pcount(26,0);
        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;
    }

[1973719588]

from collections import Counter

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        ans = []

        ctp = Counter(p)
        dicp = dict(ctp)
        l = len(p)

        for x in s[0:l]:
            if x in dicp:
                dicp[x] -= 1

        if set(dicp.values()) == {0}:
            ans.append(0)

        for i in range(l , len(s)):
            if s[i] in dicp:
                dicp[s[i]] -= 1
            if s[i - l] in dicp:
                dicp[s[i - l]] += 1
            if set(dicp.values()) == {0}:
                ans.append(i-l+1)

        # print(ans)
        return ans

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