找到字符串中所有字母异位词-python-滑动窗口
·
题目:

思路:
- 初始化一个26位的数组count计算字符出现的个数,在s中出现+1,在p中出现-1,统计count中不为0的个数为differ,如果differ为0为一个答案。窗口滑动1位,相当于remove当前的第i位,加入第i+len(p)位。
- 判断remove后,count对应的count[ord(i)-97]是否为0,若为0,表示移除得好,differ-1;若为-1,表示移除得不好,differ+1。
- 判断加入第i+len(p)位后,count对应的count[ord(i+p_len)-97]是否为0,若为0,表示正好就差这个字符,differ-1;若为1,表示本来在s和p中出现的次数是一样的,加上反而多了,differ+1
代码:
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
s_len, p_len = len(s), len(p)
if s_len < p_len: #一定要加
return []
ans = []
count = [0] * 26
for i in range(p_len):
count[ord(s[i]) - 97] += 1
count[ord(p[i]) - 97] -= 1
differ = [c != 0 for c in count].count(True)
if differ == 0:
ans.append(0)
for i in range(s_len - p_len):
count[ord(s[i]) - 97] -= 1
if count[ord(s[i]) - 97] == 0: # 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
differ -= 1
elif count[ord(s[i]) - 97] == -1: # 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
differ += 1
count[ord(s[i + p_len]) - 97] += 1
if count[ord(s[i + p_len]) - 97] == 0: # 窗口中字母 s[i+p_len] 的数量与字符串 p 中的数量从不同变得相同
differ -= 1
elif count[ord(s[i + p_len]) - 97] == 1: # 窗口中字母 s[i+p_len] 的数量与字符串 p 中的数量从相同变得不同
differ += 1
if differ == 0:
ans.append(i + 1)
return ans
注意:
举个例子:
s="aabc",p="cb"
count[0]=2(a),count[1]=-1(b),count[3]=-1(c)
这里的count出现为2的情况不用考虑,直接i++了
更多推荐
所有评论(0)