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

[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 and

[Yukibei]

class Solution { public: vector 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;
}

};

[Lizhao-Liu]

func findAnagrams(_ s: String, _ p: String) -> [Int] {
    guard !s.isEmpty && !p.isEmpty && s.count >= p.count else { return [] }

    let length = p.count
    var res = [Int]()

    var window = [Character : Int]()
    var pDict = [Character : Int]()

    var sArray = Array(s)

    for c in p {
        pDict[c, default: 0] += 1
    }

    for r in 0..<s.count {
        if r >= length {
            var i = r - length
            window[sArray[i]] = window[sArray[i]]! - 1
            if window[sArray[i]] == 0 {
                window.removeValue(forKey: sArray[i])
            }
        }

        let character = sArray[r]
        window[character, default: 0] += 1 
        if window == pDict {
            res.append(r - length + 1)
        }
    }

    return res
}

[lxy1108]

思路

滑动窗口的同时计算当前窗口和p子串中字符个数是否相同

python3代码

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(s)<len(p):
            return []
        p_arr = [0]*26
        for ch in p:
            # print(ch,ord(ch)-ord('a'),ord('y'),ord(ch))
            p_arr[ord(ch)-ord('a')]+=1
        s_arr = [0]*26
        for ch in s[:len(p)]:
            s_arr[ord(ch)-ord('a')]+=1
        rs = []
        if s_arr==p_arr:
            rs.append(0)
        if len(s)==len(p):
            return rs
        for pointer in range(1,len(s)-len(p)+1):
            s_arr[ord(s[pointer-1])-ord('a')]-=1
            s_arr[ord(s[pointer+len(p)-1])-ord('a')]+=1
            if s_arr==p_arr:
                rs.append(pointer)
        return rs

[Dtjk]

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

[GReyQT]

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int left = 0;
        int right = 0;
        vector<int> ans;
        unordered_map<char, int> window;
        unordered_map<char, int> need;
        for (char c : p) need[c]++;
        int cnt = 0;
        while (right < s.size()) {
            char r_char = s[right];
            if (need.count(r_char)) {
                window[r_char]++;
                if (window[r_char] == need[r_char]) {
                    cnt++;
                }
            }
            if (right - left + 1 > p.size()) {
                char l_char = s[left];
                if (need.count(l_char)) {
                    if (window[l_char] == need[l_char]) {
                        cnt--;
                    }
                    window[l_char]--;
                }
                left++;
            }
            if (cnt == need.size()) {
                ans.push_back(left);
            }
            right++;
        }
        return ans;
    }
};

[Hermione666]

class Solution: def findAnagrams(self, s: str, t: str) -> List[int]: need = {} for char in t: if char in need: need[char] += 1 else: need[char] = 1

    window = {}
    left, right = 0, 0
    valid = 0
    res = []

    while right < len(s):
        c = s[right]
        right += 1
        if c in need:
            if c in window:
                window[c] += 1
            else:
                window[c] = 1
            if window[c] == need[c]:
                valid += 1

        while right - left >= len(t):
            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