一、题目
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
二、示例
2.1> 示例 1:
【输入】 s = "cbaebabacd", p = "abc"
【输出】 [0,6]
【解释】
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
2.2> 示例 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仅包含小写字母
三、解题思路
根据题目描述，我们需要在字符串s中寻找p的异位词，那么我们可以通过双指针的方式，来进行对比和判断。
【head指针】指向异位词子串的头元素，初始值为
0；
【tail指针】指向异位词子串的尾元素的下一个元素位置，初始值为0；
首先，我们创建128长度的数组int[] chars，然后遍历字符串p的每一个字符，并将对应的chars数组下标位置的值进行加1操作；
初始化完数组chars之后，我们就可以通过遍历字符串s的每个字符，来判断是否符合异位词子串了。具体逻辑如下所示：
【逻辑1】如果tail指针指向的字符，在chars中对应的值大于0，则执行
减1操作，并且执行tail++；
【逻辑2】否则，获得head指针指向的字符，然后针对该字符在chars数组中的位置处执行加1操作，并且执行head++；
【逻辑3】当满足逻辑1的情况下，我们判断如果tail减去head等于p的长度，那么就说明我们找到了p的异位词子串，则将head复制给结果List即可。
好了，上面就是整道题的解题逻辑，我们还是通过举例来加深本题的理解。假设我们输入s = "cbaebabacd", p = "abc"，针对前3个字符，我们发现都能在chars中找到，即：满足逻辑1。所以tail一直会移动到第3个下标位置。并且此时chars中所有元素都为0；
因为chars数组中所有元素都是0，所以，满足逻辑2。那么head指针会进行移动，并且针对head指向的字符，都会在chars数组中进行加1操作。由于文章篇幅问题，仅画出了tail指针和head指针的移动过程。那么其余步骤就不再画了，并不影响对整道题目的理解。
四、代码实现
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList();
int[] chars = new int[128];
for (char c : p.toCharArray()) chars[c]++;
int head = 0, tail = 0;
char[] sc = s.toCharArray();
while (tail < sc.length) {
if (chars[sc[tail]] > 0) {
chars[sc[tail++]]--;
if ((tail - head) == p.length()) result.add(head);
} else chars[sc[head++]]++;
}
return result;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论