給定兩個字符串?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" 的異位詞。

?解法一：

# 解題思路：hash表、雙指針、滑動窗口
class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:# 首先判斷特殊情況if len(p) > len(s):return []ans=[]# 字符串字典化，方便后續對比cnt_p = defaultdict(int)for a in p:cnt_p[a]+=1p_len=len(p)# 初始化一個長度為p的窗口字典cnt_window = defaultdict(int)for b in range(p_len):cnt_window[s[b]]+=1# 如果和初始化窗口字典相同，那么其實位置就是0if cnt_p==cnt_window:ans.append(0)s_len=len(s)# 為什么從p_len開始？為什么left=right-p_len,這樣[left,right]的窗口長度不就大于len(p)了嗎?# 回答上面的問題，因為在對比cnt_window和cnt_p前，先執行了cnt_window[s[left]]-=1，實際起始位置是left+1for right in range(p_len,s_len):left = right-p_lencnt_window[s[right]]+=1cnt_window[s[left]]-=1# 這個是為了防止在對比時，出現value=0的情況，影響對比if cnt_window[s[left]]==0:del cnt_window[s[left]]if cnt_window==cnt_p:ans.append(left+1)return ans

解法二：

class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:ans=[]# 創建一個字符計數的字典cnt_p = Counter(p)cnt_window = Counter()for right,c in enumerate(s):left=right-len(p)+1cnt_window[c]+=1if left<0:continueif cnt_window==cnt_p:ans.append(left)cnt_window[s[left]]-=1return ans

?

?