題目
難度：★★☆☆☆
類型：字符串
給定一個(gè)字符串 s 和一個(gè)非空字符串 p，找到 s 中所有是 p 的字母異位詞的子串，返回這些子串的起始索引。
字符串只包含小寫英文字母，并且字符串 s 和 p 的長度都不超過 20100。
說明
字母異位詞指字母相同，但排列不同的字符串。
不考慮答案輸出的順序。
示例
示例 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" 的字母異位詞。
解答
這道題是【題目242. 有效的字母易位詞】的進(jìn)階版，這里不僅要實(shí)現(xiàn)字母易位詞的判別功能，而且要尋找出某一個(gè)長串中所有的字母易位詞。
關(guān)于字母易位詞。首先回顧一下字母易位詞的判別條件：如果兩個(gè)字符串中每個(gè)字符出現(xiàn)的次數(shù)均相同，那么這兩個(gè)字符串互為字母易位詞，例如"aabcc"與"accba"就互為字母易位詞。技術(shù)實(shí)現(xiàn)上，我們可以通過python中collections模塊中的Counter函數(shù)得到某一個(gè)字符串中每個(gè)字符出現(xiàn)次數(shù)的統(tǒng)計(jì)，如果字符串s1和s2的統(tǒng)計(jì)結(jié)果Counter(s1)==Counter(s2)，那么s1和s2就互為字母易位詞。
滑動(dòng)窗口。這里，我們要在字符串p中找到字符串s的字母易位詞，可以在字符串s中構(gòu)建一個(gè)長度與p一致的滑窗，從頭到尾劃過字符串s，在滑動(dòng)的過程中，我們可以判別滑窗范圍內(nèi)的子串是否是p的字母易位詞，如果是，則將滑窗左端位置添加到結(jié)果列表中。
計(jì)數(shù)器。我們準(zhǔn)備了一個(gè)計(jì)數(shù)器字典，用于記錄滑窗中子串各個(gè)字符出現(xiàn)次數(shù)，這里為了減少計(jì)算量，我們并非每次都對滑窗進(jìn)行字符統(tǒng)計(jì)，而是只對計(jì)數(shù)器中新加入的字符和剛刪除的字符進(jìn)行處理。
from collections import Counter
from collections import Counter
class Solution(object):
def findAnagrams(self, s, p):
p_count = Counter(p) # 對字符串p中的字符進(jìn)行計(jì)數(shù)
s_count = Counter(s[:len(p)-1]) # 對字符串s中前l(fā)en(p)個(gè)字符進(jìn)行計(jì)數(shù)
ans = [] # 結(jié)果列表，用于保存s中p的易位詞出現(xiàn)位置
for i in range(len(p)-1, len(s)): # 從p的長度開始遍歷到s的長度
# s[i]從右邊進(jìn)入滑動(dòng)窗口
s_count[s[i]] += 1 # 更新字符計(jì)數(shù)器s_count中s[i]的出現(xiàn)次數(shù)
cur_idx = i - len(p) + 1 # 滑動(dòng)窗口左端元素在s中的位置
cur_char = s[cur_idx] # 滑動(dòng)窗口左端元素
# 易位詞判別，比較窗口中字符串s[cur_idx:i]和目標(biāo)字符串p是否互為易位詞
if s_count == p_count:
ans.append(cur_idx) # 如果是，則將滑動(dòng)窗口左端位置加入到結(jié)果列表中
s_count[cur_char] -= 1 # 將滑動(dòng)窗口左端元素從窗口中彈出，更新字符計(jì)數(shù)器
if s_count[cur_char] == 0: # 如果彈出后計(jì)數(shù)器中出現(xiàn)次數(shù)變?yōu)榱? del s_count[cur_char] # 從計(jì)數(shù)器中刪除該字符
return ans
如有疑問或建議，歡迎評(píng)論區(qū)留言~
