找到字符串中所有字母异位词
题目要求
本题目的目标是在给定的字符串 s 中寻找所有与字符串 p 为异位词的子串，并返回这些子串的起始索引。这里的异位词是指一个字符串的字符重新排列后可以得到另一个字符串，即两个字符串中的字符种类和字符数量都是相同的，但是字符的顺序可以不同。
解题思路
要解决这个问题，可以采用滑动窗口的策略，结合字符计数的方法。以下是解题的步骤：
-
字符计数：首先，对字符串 p 中的每个字符进行计数，得到一个计数器（通常是哈希表或固定大小的数组），记录每个字符出现的次数。
-
初始化滑动窗口：初始化一个与字符串 p 长度相同的滑动窗口，用于在字符串 s 中滑动。同时，创建一个计数器用于记录当前窗口内的字符出现次数。
-
滑动窗口：将滑动窗口从字符串 s 的起始位置滑动到结束位置，每次移动一位。对于每个新进入窗口的字符，增加该字符在窗口计数器中的计数；对于移出窗口的字符，减少该字符在窗口计数器中的计数。
-
匹配检查：在每次窗口滑动后，比较窗口计数器与字符串 p 的计数器是否相同。如果相同，说明当前窗口内的子串是字符串 p 的一个异位词，将当前窗口的起始索引添加到结果列表中。
-
返回结果：遍历完字符串 s 后，返回结果列表，即为所有异位词子串的起始索引。
这种方法的时间复杂度主要取决于字符串 s 的长度和字符集的大小，但由于每次窗口移动只需要常数时间的更新，因此是效率较高的解法。
Golang 版本
package main
import (
"fmt"
)
func findAnagrams(s string, p string) []int {
var res []int
pCount, sCount := [26]int{}, [26]int{}
pLen, sLen := len(p), len(s)
// 如果p的长度大于s的长度，直接返回空结果
if pLen > sLen {
return res
}
// 初始化字符计数器
for i := 0; i < pLen; i++ {
pCount[p[i]-'a']++
sCount[s[i]-'a']++
}
// 滑动窗口
for i := 0; i < sLen-pLen; i++ {
// 如果计数器相同，则添加起始索引
if pCount == sCount {
res = append(res, i)
}
// 窗口滑动，更新计数器
sCount[s[i]-'a']--
sCount[s[i+pLen]-'a']++
}
// 检查最后一个窗口
if pCount == sCount {
res = append(res, sLen-pLen)
}
return res
}
func main() {
s := "cbaebabacd"
p := "abc"
fmt.Println(findAnagrams(s, p)) // 输出异位词的起始索引
}
这段代码定义了一个findAnagrams函数，它接受两个字符串s和p作为参数，并返回一个整数切片，包含了字符串s中所有字符串p的异位词子串的起始索引。在main函数中，我们调用了findAnagrams函数，并打印了返回的结果。
C++版本
#include <iostream>
#include <vector>
#include <string>
std::vector<int> findAnagrams(std::string s, std::string p) {
std::vector<int> res;
std::vector<int> pCount(26, 0), sCount(26, 0);
int pLen = p.length(), sLen = s.length();
// 如果p的长度大于s的长度，直接返回空结果
if (pLen > sLen) return res;
// 初始化字符计数器
for (int i = 0; i < pLen; ++i) {
++pCount[p[i] - 'a'];
++sCount[s[i] - 'a'];
}
// 滑动窗口
for (int i = 0; i < sLen - pLen; ++i) {
// 如果计数器相同，则添加起始索引
if (pCount == sCount) res.push_back(i);
// 窗口滑动，更新计数器
--sCount[s[i] - 'a'];
++sCount[s[i + pLen] - 'a'];
}
// 检查最后一个窗口
if (pCount == sCount) res.push_back(sLen - pLen);
return res;
}
int main() {
std::string s = "cbaebabacd";
std::string p = "abc";
std::vector<int> anagrams = findAnagrams(s, p);
for (int index : anagrams) {
std::cout << index << " ";
}
std::cout << std::endl;
return 0;
}
这段 C++代码实现了与 Golang 版本相同的功能。它定义了一个findAnagrams函数，用于查找字符串s中所有字符串p的异位词子串的起始索引，并在main函数中测试了这个功能。输出结果是所有异位词子串的起始索引列表。
Python 版本
from collections import Counter
def find_anagrams(s, p):
res = []
p_counter = Counter(p)
s_counter = Counter(s[:len(p) - 1])
for i in range(len(p) - 1, len(s)):
s_counter[s[i]] += 1 # include a new char in the window
if s_counter == p_counter: # This step is O(1) because there are at most 26 English letters
res.append(i - len(p) + 1) # append the starting index
s_counter[s[i - len(p) + 1]] -= 1 # decrease the count of the oldest char in the window
if s_counter[s[i - len(p) + 1]] == 0:
del s_counter[s[i - len(p) + 1]] # remove the count if it is 0
return res
# Example usage:
s = "cbaebabacd"
p = "abc"
print(find_anagrams(s, p)) # Output the starting indices of the anagrams of p in s
这段 Python 代码实现了查找字符串s中所有字符串p的异位词子串的起始索引的功能。它使用了collections.Counter来进行字符计数，并通过滑动窗口的方式来遍历字符串s。当窗口中的字符计数与字符串p的字符计数相同时，将当前窗口的起始索引添加到结果列表中。
Java 版本
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (s == null || p == null || s.length() < p.length()) {
return result;
}
int[] pCount = new int[26];
int[] sCount = new int[26];
for (int i = 0; i < p.length(); i++) {
pCount[p.charAt(i) - 'a']++;
}
for (int i = 0; i < s.length(); i++) {
if (i >= p.length()) {
sCount[s.charAt(i - p.length()) - 'a']--;
}
sCount[s.charAt(i) - 'a']++;
if (i >= p.length() - 1) {
if (matches(pCount, sCount)) {
result.add(i - p.length() + 1);
}
}
}
return result;
}
private boolean matches(int[] pCount, int[] sCount) {
for (int i = 0; i < 26; i++) {
if (pCount[i] != sCount[i]) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Solution solution = new Solution();
String s = "cbaebabacd";
String p = "abc";
List<Integer> anagrams = solution.findAnagrams(s, p);
for (int index : anagrams) {
System.out.print(index + " ");
}
}
}
这段 Java 代码定义了一个Solution类，其中包含了findAnagrams方法，用于查找字符串s中所有字符串p的异位词子串的起始索引。它还包含了一个辅助方法matches，用于比较两个字符计数数组是否相等。在main方法中，我们创建了一个Solution对象，并调用了findAnagrams方法，最后打印出了所有异位词子串的起始索引。
Rust 版本
use std::collections::HashMap; fn find_anagrams(s: String, p: String) -> Vec<i32> { let mut res = Vec::new(); let (s_len, p_len) = (s.len(), p.len()); if s_len < p_len { return res; } let (s, p) = (s.as_bytes(), p.as_bytes()); let mut p_count = [0; 26]; let mut s_count = [0; 26]; for &c in &p[..p_len] { p_count[(c - b'a') as usize] += 1; } for i in 0..s_len { if i >= p_len { s_count[(s[i - p_len] - b'a') as usize] -= 1; } s_count[(s[i] - b'a') as usize] += 1; if p_count == s_count { res.push((i + 1 - p_len) as i32); } } res } fn main() { let s = String::from("cbaebabacd"); let p = String::from("abc"); let anagrams = find_anagrams(s, p); for start_index in anagrams { println!("{}", start_index); } }
这段 Rust 代码实现了查找字符串s中所有字符串p的异位词子串的起始索引的功能。它使用了固定大小的数组来存储字符计数，利用 Rust 的字节操作来更新计数器，并在滑动窗口中比较两个计数器数组是否相等。如果相等，则将当前索引添加到结果向量中。在main函数中，我们测试了这个功能并打印了结果。
总结
上述 Rust 版本的代码实现了一个用于查找字符串中所有异位词起始索引的函数。这个解法主要包括以下几个步骤：
-
初始化变量：创建两个固定大小的数组
p_count和s_count来分别存储字符串p的字符频率和字符串s的滑动窗口中的字符频率。同时，初始化一个向量res来存储结果。 -
计算字符频率：遍历字符串
p，更新p_count数组中对应字符的频率。 -
滑动窗口遍历：通过一个循环遍历字符串
s，使用滑动窗口的方式来更新s_count数组。窗口的大小与字符串p的长度相同。 -
窗口内字符频率比较：在每次窗口滑动后，比较
p_count和s_count数组。如果两个数组相等，说明当前窗口内的子串是字符串p的一个异位词，将当前窗口的起始索引添加到结果向量res中。 -
返回结果：遍历完成后，返回向量
res，它包含了所有异位词的起始索引。
这种解法的时间复杂度为 O(n)，其中 n 是字符串s的长度，因为每个字符只被访问常数次。空间复杂度为 O(1)，因为字符频率数组的大小不依赖于输入字符串的大小，它只依赖于字符集的大小，对于英文字母字符集来说是常数。