当前位置：首页 > news >正文

【滑动窗口+哈希表/数组记录】Leetcode 438. 找到字符串中所有字母异位词

news 2025/5/19 4:47:49

题目要求

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

字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。

示例 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" 的异位词。

提示

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

实际应用

文本处理领域

假设我们有一个长文本文件，我们希望找到所有包含特定关键词的不同排列组合的子串。

例如，我们在一篇科学论文中查找包含关键词 "study"、"analysis" 和 "results" 的所有排列组合的句子。

数据清洗与分析领域

假设我们有一个 DNA 序列，我们希望查找所有包含特定碱基对（如 "ATCG"）的异位词的子序列。这在基因序列分析中非常有用，帮助识别具有相同碱基分布的模式。

滑动窗口法

要求在字符串 s 中找出所有与字符串 p 的字符频率相同的子串。

关键在于高效地比较 s 中每个可能子串的字符频率与 p 的字符频率是否相同。

哈希表记录字符频率

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;vector<int> findAnagrams(string s, string p)
{unordered_map<char, int> need, window;for (char c : p)need[c]++;int left = 0, right = 0, valid = 0;vector<int> res; // 记录结果while (right < s.size()){char c = s[right];right++;// 进行窗口内数据的一系列更新if (need.count(c)){window[c]++;if (window[c] == need[c])valid++;}// 判断左侧窗口是否要收缩while (right - left >= p.size()){// 当窗口符合条件时，把起始索引加入结果集if (valid == need.size())res.push_back(left);char d = s[left];left++;// 进行窗口内数据的一系列更新if (need.count(d)){if (window[d] == need[d])valid--;window[d]--;}}}return res;
}int main(){string s = "cbaebabacd";string p = "abc";vector<int> res = findAnagrams(s,p);for(auto i:res){cout<<i<<endl;}return 0;
}

数组记录字符频率

#include <iostream>
#include <vector>
using namespace std;vector<int> findAnagrams(string s, string p)
{vector<int> need(26, 0);vector<int> window(26, 0);for (char c : p){need[c - 'a']++;}int left = 0, right = 0, valid = 0;vector<int> res;// required表示窗口中需要满足的字符种类数int required = 0;for (int i = 0; i < 26; ++i){if (need[i] > 0){required++;}}while (right < s.size()){char c = s[right];right++;if (need[c - 'a'] > 0){window[c - 'a']++;// 当窗口中某个字符的数量等于需要的数量时，valid++if (window[c - 'a'] == need[c - 'a']){valid++;}}// 当窗口大小等于p的长度时，判断是否需要收缩while (right - left >= p.size()){// 当窗口中满足要求的字符种类数等于required时，将窗口的起始位置加入结果if (valid == required){res.push_back(left);}char d = s[left];left++;if (need[d - 'a'] > 0){// 当窗口中某个字符的数量等于需要的数量时，valid--if (window[d - 'a'] == need[d - 'a']){valid--;}window[d - 'a']--;}}}return res;
}int main()
{string s = "cbaebabacd";string p = "abc";vector<int> res = findAnagrams(s, p);for (auto i : res){cout << i << endl;}return 0;
}