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

[freesan44]

class Solution {
    func findAnagrams(_ s: String, _ p: String) -> [Int] {
        var target = [Character: Int]()
        var ans = [Int]()

        for char in p {
            target[char, default: 0] += 1
        }

        for i in 0..<s.count {
            if i >= p.count {
                let charToRemove = s[s.index(s.startIndex, offsetBy: i - p.count)]
                target[charToRemove] = (target[charToRemove] ?? 0) + 1
                if target[charToRemove] == 0 {
                    target[charToRemove] = nil
                }
            }

            let charToAdd = s[s.index(s.startIndex, offsetBy: i)]
            target[charToAdd, default: 0] -= 1
            if target[charToAdd] == 0 {
                target[charToAdd] = nil
            }

            if target.isEmpty {
                ans.append(i - p.count + 1)
            }
        }

        return ans
    }
}

[GuitarYs]

from collections import Counter

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

        left = 0
        current = Counter(s[:len(p)])

        while left <= len(s) - len(p):
            if current == target:
                result.append(left)

            if current[s[left]] > 1:
                current[s[left]] -= 1
            else:
                del current[s[left]]

            if left + len(p) < len(s):
                current[s[left + len(p)]] += 1

            left += 1

        return result

[catkathy]

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        HashMap<Character, Integer> window_map = new HashMap<>();
        HashMap<Character, Integer> p_map = new HashMap<>();
        for (int i = 0; i < p.length(); i++){
            char c1 = p.charAt(i);
            p_map.put(c1, p_map.getOrDefault(c1, 0) + 1);
        }
        int left, right, count;
        left = right = count = 0;
        ArrayList<Integer> res = new ArrayList<>();

        while(right < s.length()){
            char c = s.charAt(right);
            right++;
            if (p_map.containsKey(c)){
                window_map.put(c, window_map.getOrDefault(c, 0) + 1);
                if(window_map.get(c).equals(p_map.get(c))){
                    count++;
                }
            }
            while(right - left == p.length()){
                if (count == p_map.size()){
                    res.add(left);
                }
                char d = s.charAt(left);
                left++;
                if (p_map.containsKey(d)){
                    if (window_map.get(d).equals(p_map.get(d))){
                        count--;
                    }
                    window_map.put(d, window_map.getOrDefault(d, 0) -1);
                }
            } 
        }
        return res;  
    }
}

[jennyjgao]

public class MedianFindAnagrams438 {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<Integer>();
        if (s.length() < p.length()) {
            return res;
        }
        int[] pcount = new int[26];
        int[] scount = new int[26];

        for (int i = 0; i < p.length(); i++) {    //记录第一组p长度的字符是否符合条件
            scount[s.charAt(i) - 'a']++;
            pcount[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(scount, pcount)) {
            res.add(0);
        }
        for (int i = 0; i < s.length() - p.length(); i++) {    //将第一组的第一个字符数量减去
            scount[s.charAt(i) - 'a']--;
            //将窗口移动到第二组的最后一个字符的位置
            scount[s.charAt(i + p.length()) - 'a']++;
            if (Arrays.equals(scount, pcount)) {
                res.add(i + 1);
            }
        }
        return res;
    }
}

[Beanza]

class Solution { func findAnagrams( s: String, p: String) -> [Int] { var target = [Character: Int]() var ans = [Int]()

    for char in p {
        target[char, default: 0] += 1
    }

    for i in 0..<s.count {
        if i >= p.count {
            let charToRemove = s[s.index(s.startIndex, offsetBy: i - p.count)]
            target[charToRemove] = (target[charToRemove] ?? 0) + 1
            if target[charToRemove] == 0 {
                target[charToRemove] = nil
            }
        }

        let charToAdd = s[s.index(s.startIndex, offsetBy: i)]
        target[charToAdd, default: 0] -= 1
        if target[charToAdd] == 0 {
            target[charToAdd] = nil
        }

        if target.isEmpty {
            ans.append(i - p.count + 1)
        }
    }

    return ans
}

}

[Fuku-L]

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if(s.length() < p.length()){
            return new ArrayList<Integer>();
        }
        List<Integer> res = new ArrayList<>();
        int sLen = s.length();
        int pLen = p.length();
        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']++;
        }
        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;
    }
}

[Diana21170648]

思路

滑动窗口

代码

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)，其中 N 为str长度。
• 空间复杂度：O(1)

[Alexno1no2]

from typing import List
from collections import defaultdict

class Solution:
    def findAnagrams(self,s: str, t: str) -> List[int]:
        need, window = defaultdict(int), defaultdict(int)
        for c in t:
            need[c] += 1

        left, right = 0, 0
        valid = 0
        res = []
        while right < len(s):
            c = s[right]
            right += 1
            # 进行窗口内数据的一系列更新
            if c in need:
                window[c] += 1
                if window[c] == need[c]:
                    valid += 1
            # 判断左侧窗口是否要收缩
            while right - left >= len(t):
                # 当窗口符合条件时，把起始索引加入 res
                if valid == len(need):
                    res.append(left)
                d = s[left]
                left += 1
                # 进行窗口内数据的一系列更新
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1

        return res

[zhaoygcq]

思路

滑动窗口；

代码

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    let origin = countStr(p);
    let res = [];
    let len = p.length;
    for(let i = 0; i <= s.length - len; i++) {
        let temp = countStr(s.slice(i, i+len), Object.assign({}, origin));

        if(temp) {
            res.push(i);
        }
    }
    return res;
};

function countStr(str, map) {
    if(map) {
        for(let val of str) {
            if(!map[val]) return false;
            map[val]--;
        }
        return true;
    } else {
        let res = {};
        for(let val of str) {
            if(!res[val]) {
                res[val] = 0;
            }
            res[val]++;
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(KN)，其中 N 为s的长度， K为p的长度。
• 空间复杂度：O(K)

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

[yetfan]

代码

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

[HuiyingC]

思路

• Sliding window: enumerate s; i >= CONDITION: 更新ans；更新win
• 字符串字典：[0 for i in range(26)]; ord(ch)-ord('a')

Code

def findAnagrams(self, s, p):
    len_s, len_p = len(s), len(p)
    if len_s < len_p: return []

    s_list, p_list = [0 for i in range(26)], [0 for i in range(26)]
    ans = []

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

    for i, ch in enumerate(s):
        if i >= len_p:
            s_list[ord(s[i-len_p])-ord('a')] -= 1

        s_list[ord(ch)-ord('a')] += 1

        if s_list == p_list:
            ans.append(i-len_p+1)         

    return ans

Complexity

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