題目:
給定一個字符串 s 和一個非空字符串 p窄做,找到 s 中所有是 p 的字母異位詞的子串,返回這些子串的起始索引。
字符串只包含小寫英文字母,并且字符串 s 和 p 的長度都不超過 20100梧疲。
說明:
字母異位詞指字母相同,但排列不同的字符串运准。
不考慮答案輸出的順序幌氮。
來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)胁澳,非商業(yè)轉(zhuǎn)載請注明出處该互。
解答:
這題是滑動窗口的典型題。
首先先創(chuàng)建一個哈希表(這里用數(shù)組代替)來記錄字符串 p 中包含的字符及其數(shù)目韭畸。
緊接著創(chuàng)建頭指針和尾指針來遍歷字符串 s 宇智。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> list = new ArrayList<>();
if (s == null || s.length() == 0 || p == null || p.length() == 0)
return list;
int[] hash = new int[256]; //字符哈希表
//記錄在 t 中出現(xiàn)的字符及其次數(shù)
for (char c : p.toCharArray()) {
hash[c]++;
}
int left=0,right=0,cnt=p.length();
while(right<s.length()){
//若是遍歷到的字符在t內(nèi),應(yīng)該大于1
if(hash[s.charAt(right++)]-- >=1) cnt--;
if(cnt==0)
list.add(left);
//移動頭指針陆盘,只有當(dāng)hash的值大于0才使cnt++普筹,代表這個原來就在t內(nèi)败明。
//加1是因為頭指針前移了隘马,需要還原cnt的值
if(right-left==p.length()&&hash[s.charAt(left++)]++ >= 0) cnt++;
}
return list;
}
}