Leetcode Hot 1001 分钟
5 次阅读
找到字符串中所有字母异位词
这里写一句文章摘要。
题目
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
解答
思路
字母异位词的概念及解决方法在之前就出现过，可见LeetCode 49. 字母异位词分组 - 两种哈希表解法 | 与子同程
在该篇文章中，一共提及了两种处理字母异位词的方法，分别是排序和统计字母出现次数的方法，本题使用后者的方法进行。
由题目可知，本题需要找到子串中的字母异位词，由于字母异位词长度一定相同，故本题用一个指针进行一次遍历的同时维护一个统计字母序列，即可解决。
答案
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
p_num = [0] * 26
sub_num = [0] * 26
for ch in p:
p_num[ord(ch) - ord('a')] += 1
res = []
for i in range(len(s)):
sub_num[ord(s[i]) - ord('a')] += 1
if sub_num == p_num:
res.append(i - len(p) + 1)
if i >= len(p) - 1:
sub_num[ord(s[i - len(p) + 1]) - ord('a')] -= 1
return res