问题:
给定两个字符串 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" 的异位词。
思路和代码
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
# 可以想到用一个大小为p.length的滑动窗口,然后检查窗口内的p_tmp是否符合条件
# 因为不涉及到顺序,因此可以使用一个mapp或者26个元素的数组来存储每个字母的个数,
# 然后对比两个map是否相同
# 如果相同那么这个窗口就是符合条件的异位词
result = []
pLen = len(p)
sLen = len(s)
if pLen > sLen:
return result
p_num = [0] * 26 # 记录p的数据
tmp_num = [0] * 26 # 记录s窗口的数据
for i in range(pLen):
p_num[ord(p[i]) - ord('a')] = p_num[ord(p[i]) - ord('a')] + 1
tmp_num[ord(s[i]) - ord('a')] = tmp_num[ord(s[i]) - ord('a')] + 1
if self.isSame(tmp_num, p_num, None, None):
result.append(0)
# 遍历s
for i in range(1, sLen - pLen + 1):
if self.isSame(tmp_num, p_num, s[i - 1], s[i - 1 + pLen]):
result.append(i)
return result
def isSame(self, tmp_num, p_num, remove_char, new_char):
#print(remove_char, new_char)
if remove_char != None and new_char != None:
tmp_num[ord(remove_char) - ord('a')] -= 1
tmp_num[ord(new_char) - ord('a')] += 1
# 先判断增加和删除的字符符合,提高判断速度
if tmp_num[ord(remove_char) - ord('a')] != p_num[ord(remove_char) - ord('a')]:
return False
if tmp_num[ord(new_char) - ord('a')] != p_num[ord(new_char) - ord('a')]:
return False
for i in range(len(p_num)):
if (tmp_num[i] != p_num[i]):
return False
return True
文章评论