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

[Fightforcoding]

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        k = len(p)
        if len(p) > len(s):
            return None
        p_count = Counter(p)
        s_count = Counter()
        result = []
        for i in range(len(s)):
            s_count[s[i]] += 1
            if i >= k:
                left = s[i-k]
                s_count[left] -=1
                if s_count[left] == 0:
                    del s_count[left]
            if s_count == p_count:
                result.append(i - k + 1) 

        return result

``` Time O(N), 

space O(1)

[qiaoeve]

思路：将字符串转换成数组，遍历s比较与p长度一样的字符子串，通过哈希表可以确保包含的不同字符数量一致， 在不同字符数量一致后，通过字典作差，如果所有字符的差都为0，说明即使重复出现，也是一致的 class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: se = [] for i in s: se.append(i)

    pe = []
    for i in p:
        pe.append(i)

    dic_countp = collections.Counter(pe)
    seen = set(pe)
    indexs = []

    for j in range(len(se) - len(pe) + 1):
        list_s = se[j:j + len(pe)]
        dic_counts = collections.Counter(list_s)
        seen1 = set(list_s)
        result = {k: dic_countp[k] - dic_counts[k] for k in dic_countp if k in dic_counts}
        if not seen1 - seen and not seen-seen1 and all(v == 0 for v in result.values()):
            indexs.append(j)
    return indexs

时间复杂度：O（M*N）

[zjy-debug]

代码

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        # 结果列表
        result = []

        # 统计 p 中字符的频率
        p_count = [0] * 26
        for char in p:
            p_count[ord(char) - ord("a")] += 1

        # 当前窗口的字符频率
        s_count = [0] * 26
        p_length = len(p)

        for i in range(len(s)):
            # 添加当前字符到窗口
            s_count[ord(s[i]) - ord("a")] += 1

            # 如果窗口大小超过 p 的长度，移除左边的字符
            if i >= p_length:
                s_count[ord(s[i - p_length]) - ord("a")] -= 1

            # 如果窗口大小等于 p 的长度，进行比较
            if i >= p_length - 1:
                if s_count == p_count:
                    result.append(i - p_length + 1)

        return result

[sleepydog25]

Approach

sliding window

Algo

  List<Integer> result = new ArrayList<>();
        int pLength = p.length();
        int sLength = s.length();

        // Edge case: if s is shorter than p, return empty list
        if (sLength < pLength) return result;

        // Sort the target string p
        char[] pArray = p.toCharArray();
        Arrays.sort(pArray);
        String sortedP = new String(pArray);

        // Sliding window to check each substring of s
        for (int i = 0; i <= sLength - pLength; i++) {
            String currentSubstring = s.substring(i, i + pLength);
            char[] currentArray = currentSubstring.toCharArray();
            Arrays.sort(currentArray);
            String sortedCurrent = new String(currentArray);

            if (sortedCurrent.equals(sortedP)) {
                result.add(i);
            }
        }

        return result;

Complexity

1. time complexity:
2. space complexity:

[godkun]

思路

• 滑动窗口

代码

PY实现

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        pLen = len(p)
        arr = sorted(p)
        res = []
        c = []
        for i in range(0, len(s) - pLen + 1):
            c = sorted(s[i : i + pLen])
            if c == arr:
                res.append(i)
        return res

复杂度分析

时间复杂度：O(N∗M∗Log(M)) 空间复杂度：O(N)