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

题解思路

本题是一个滑动窗口问题，要求找出所有 p 的异位词（即字符相同但顺序不同的子串）在 s 中的起始索引。

1. 使用固定大小的滑动窗口

由于 p 的所有异位词长度固定为 len(p)，可以使用固定大小的滑动窗口遍历 s。

• 维护一个 p 的字符计数 p_count（字典或数组）。
• 维护一个 s 的窗口 s_count，长度等于 p，表示当前窗口中的字符频率。
• 如果 s_count 和 p_count 相等，则记录起始索引。

2. 滑动窗口优化

• 在遍历 s 时，不需要每次都重新计算整个窗口的字符统计，而是仅调整新增字符和移除的字符：
  • 添加新进入窗口的字符
  • 移除滑出窗口的字符
  • 比较 s_count 和 p_count 是否相等

这样，每次滑动窗口的操作时间复杂度降低到 O(1)。

时间复杂度分析

• 初始化 p_count 和 s_count 需要 O(m)，其中 m 是 p 的长度。
• 滑动窗口遍历 s 需要 O(n)。
• 比较两个哈希表（数组） 需要 O(1)（因为最多26个字母）。
• 总时间复杂度 为 O(n+m)。
• 空间复杂度为 O(26)。

代码

Python 代码

from collections import Counter

class Solution:
    def findAnagrams(self, s: str, p: str):
        p_len, s_len = len(p), len(s)
        if s_len < p_len:
            return []

        # 记录 p 的字符计数
        p_count = Counter(p)
        s_count = Counter(s[:p_len])  # 统计第一个窗口的字符

        res = []
        if p_count == s_count:
            res.append(0)

        for i in range(p_len, s_len):
            # 新增字符
            s_count[s[i]] += 1
            # 移除窗口左端字符
            s_count[s[i - p_len]] -= 1
            if s_count[s[i - p_len]] == 0:
                del s_count[s[i - p_len]]

            # 检查窗口是否匹配
            if s_count == p_count:
                res.append(i - p_len + 1)

        return res

# 读取输入
s = input().strip()
p = input().strip()
solution = Solution()
result = solution.findAnagrams(s, p)
print(" ".join(map(str, result)))

Java 代码

import java.util.*;

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

            List<Integer> res = new ArrayList<>();
            int[] pCount = new int[26]; // 记录 p 的字符频率
            int[] sCount = new int[26]; // 记录 s 当前窗口的字符频率

            // 统计 p 和 s 的第一个窗口
            for (int i = 0; i < pLen; i++) {
                pCount[p.charAt(i) - 'a']++;
                sCount[s.charAt(i) - 'a']++;
            }

            // 检查第一个窗口是否匹配
            if (Arrays.equals(pCount, sCount)) res.add(0);

            // 滑动窗口
            for (int i = pLen; i < sLen; i++) {
                sCount[s.charAt(i) - 'a']++;         // 新增窗口内字符
                sCount[s.charAt(i - pLen) - 'a']--;  // 移除窗口左端字符

                // 检查窗口是否匹配
                if (Arrays.equals(pCount, sCount)) {
                    res.add(i - pLen + 1);
                }
            }

            return res;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String p = scanner.nextLine();
        scanner.close();

        Main main = new Main();
        Solution solution = main.new Solution();
        List<Integer> result = solution.findAnagrams(s, p);

        for (int idx : result) {
            System.out.print(idx + " ");
        }
    }
}

C++ 代码

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

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

        vector<int> res;
        vector<int> pCount(26, 0), sCount(26, 0);

        // 统计 p 和 s 的第一个窗口
        for (int i = 0; i < pLen; i++) {
            pCount[p[i] - 'a']++;
            sCount[s[i] - 'a']++;
        }

        // 检查第一个窗口是否匹配
        if (pCount == sCount) res.push_back(0);

        // 滑动窗口
        for (int i = pLen; i < sLen; i++) {
            sCount[s[i] - 'a']++;        // 新增窗口内字符
            sCount[s[i - pLen] - 'a']--; // 移除窗口左端字符

            // 检查窗口是否匹配
            if (pCount == sCount) {
                res.push_back(i - pLen + 1);
            }
        }

        return res;
    }
};

int main() {
    string s, p;
    cin >> s >> p;

    Solution solution;
    vector<int> result = solution.findAnagrams(s, p);

    for (int idx : result) {
        cout << idx << " ";
    }

    return 0;
}

Leetcode 9.找到字符串中所有字母异位词-原题链接

题目内容

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

输入描述

输入共两行。

• 第一行为字符串$s$

• 第二行为字符串$p$

输出描述

输出为一行，包含所有满足条件的子串的起始索引，索引之间用空格分隔。索引的顺序可以是任意的，但必须包含所有符合条件的索引。

样例1

输入

cbaebabacd
abc

输出

0 6

说明

起始索引等于 $0$的子串是 "$cba$", 它是 "$abc$" 的异位词。 起始索引等于 $6$的子串是 "$bac$", 它是 "$abc$" 的异位词。

样例2

输入

abab
ab

输出

0 1 2

说明

起始索引等于 $0$ 的子串是 "$ab$", 它是 "$ab$" 的异位词。

起始索引等于 $1$ 的子串是 "$ba$", 它是 "$ab$" 的异位词。

起始索引等于 $2$ 的子串是 "$ab$", 它是 "$ab$" 的异位词。

提示

• $1 <= s.length, p.length <= 3 * 10^4$
• $s$和 $p$仅包含小写字母