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: