438.找出字符串中所有字母异位词
题目:
给定两个字符串 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" 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104
s
和p
仅包含小写字母
解题思路:
将滑动窗口的大小设置为p的长度,如果s的长度或者s的剩余长度小于p直接返回,否则将窗口内的字母进行排序,如果排序得到的结果是相同的就认为是异位词
代码:
class Solution:
def findAnagrams(self, s: str, p: str):
len_s, len_p = len(s), len(p)
if len_s<len_p:
return []
p_sorted = sorted(p)
outputs = []
for i in range(len(s)):
if len_s-i<len_p:
return outputs
s_sorted = sorted(s[i:i+len(p)])
if s_sorted==p_sorted:
outputs.append(i)
return outputs
官方代码:
# 官方代码
class Solution:
def findAnagrams(self, s: str, p: str):
s_len, p_len = len(s), len(p)
# 如果s的长度比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):
# 遍历s得到字母,如果在count中该字母的数量为1,则认为当前s和p中该字母抵消掉了,所有存在的字母种类数-1
if count[ord(s[i]) - 97] == 1: # 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
differ -= 1
# 遍历s得到字母,如果在count中该字母的数量为0,则认为p中没有这个字母而s中有这个字母,s的字母种类数+1
elif count[ord(s[i]) - 97] == 0: # 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
differ += 1
# 遍历过s的字母之后将字母的个数-1
count[ord(s[i]) - 97] -= 1
# 利用滑动窗口来保证字母的种类相同,如果窗口的字母的个数及字母的种类和p的字母的个数及字母的种类相同则认为是一个异位词
if count[ord(s[i + p_len]) - 97] == -1: # 窗口中字母 s[i+p_len] 的数量与字符串 p 中的数量从不同变得相同
differ -= 1
elif count[ord(s[i + p_len]) - 97] == 0: # 窗口中字母 s[i+p_len] 的数量与字符串 p 中的数量从相同变得不同
differ += 1
count[ord(s[i + p_len]) - 97] += 1
if differ == 0:
ans.append(i + 1)
return ans