题目
给定两个字符串 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 仅包含小写字母
分析
通过滑动窗口，我们取找到匹配p字符的子串，然后找下一个子串的位置。
代码
滑动窗口
p串哈希化，然后滑动p.length的窗口。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
// p 串预处理
char[] chars = p.toCharArray();
Arrays.sort(chars);
int[] charInts = new int[26];
for (char ch : chars) {
charInts[ch - 'a']++;
}
// 滑动窗口识别目标子串
int l = 0, r = 0;
List<Integer> ans = new ArrayList<>();
while (l < s.length() - p.length() + 1) {
// 移除明显不符合异构的case
if (charInts[s.charAt(l) - 'a'] > 0) {
// copy p串的hash统计
int[] temp = Arrays.copyOf(charInts, 26);
int count = 0;
// 获取子串
char[] char1 = s.substring(l, l + chars.length).toCharArray();
// 逐个匹配
for (int i = 0; i < char1.length; i++) {
if (temp[char1[i] - 'a'] > 0) {
count++;
temp[char1[i] - 'a']--;
} else {
count = 0;
break;
}
}
// count = p.length() 说明是异构串，添加下标到结果
if (count == p.length()) {
ans.add(l);
}
}
l++;
}
return ans;
}
}
窗口哈希化
对窗口构建hash存储。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
// 左右指针
int sLen = s.length(), pLen = p.length();
if (sLen < pLen) {
return new ArrayList<Integer>();
}
// 数组哈希存储字符的计数
List<Integer> ans = new ArrayList<Integer>();
int[] sCount = new int[26];
int[] pCount = new int[26];
for (int i = 0; i < pLen; ++i) {
++sCount[s.charAt(i) - 'a'];
++pCount[p.charAt(i) - 'a'];
}
// 判断刚开始是否找到异构子串
if (Arrays.equals(sCount, pCount)) {
ans.add(0);
}
// 逐个遍历，窗口大小是pLen
for (int i = 0; i < sLen - pLen; ++i) {
--sCount[s.charAt(i) - 'a'];
++sCount[s.charAt(i + pLen) - 'a'];
// 找到异构字符串
if (Arrays.equals(sCount, pCount)) {
ans.add(i + 1);
}
}
return ans;
}
}
优化窗口对比的方法
窗口的异同，采用差分法判断异构字符串。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length(), pLen = p.length();
if (sLen < pLen) {
return new ArrayList<Integer>();
}
List<Integer> ans = new ArrayList<Integer>();
int[] count = new int[26];
for (int i = 0; i < pLen; ++i) {
++count[s.charAt(i) - 'a'];
--count[p.charAt(i) - 'a'];
}
// 查分法
int differ = 0;
for (int j = 0; j < 26; ++j) {
if (count[j] != 0) {
++differ;
}
}
if (differ == 0) {
ans.add(0);
}
for (int i = 0; i < sLen - pLen; ++i) {
if (count[s.charAt(i) - 'a'] == 1) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
--differ;
} else if (count[s.charAt(i) - 'a'] == 0) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
++differ;
}
--count[s.charAt(i) - 'a'];
if (count[s.charAt(i + pLen) - 'a'] == -1) { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
--differ;
} else if (count[s.charAt(i + pLen) - 'a'] == 0) { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
++differ;
}
++count[s.charAt(i + pLen) - 'a'];
if (differ == 0) {
ans.add(i + 1);
}
}
return ans;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
