438. Find All Anagrams in a String
给你一个字串s和p,若s的某个子字串可以由p的字符排列后得到,返回s的子字串第一个
字符的索引值。
Example :
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
s[0:2]="cba" 可以被p组合所以加入0
s[6:8]="bac" 可以被p组合所以加入6
思路:
1.首先,若p的长度大于s则必不存在解,所以可以直接返回。
2.因为p可以任意排列所以我们只关心他的字母数量,我们可以维护一个基于s的
滑动窗口,每次加入一个元素,如果s的字母数量大于p就把最左边的字母从窗口
去除并更新窗口左边界,直到窗口的字母数量小于等于目标数量。
3.如果窗口的大小刚好等于p那就表示有一个子字串满足条件,将left加入结果集,
当右边的指标跑完s就可以得到解了。
Java Code: