#P4008. 找到字符串中所有字母异位词
-
ID: 2215
Tried: 325
Accepted: 86
Difficulty: 4
找到字符串中所有字母异位词
题目内容
给定两个字符串 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∗104
- s和 p仅包含小写字母
找到字符串中所有字母异位词
题解思路
本题是一个滑动窗口问题，要求找出所有 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;
}