LeetCode09：找到字符串中所有字母异位词

LeetCode09：找到字符串中所有字母异位词

题目

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

1
2
3
4
5
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

1
2
3
4
5
6
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

题解

我的解法

使用的是双层for循环，通过将p字符串的字母添加到列表，再依次遍历s字符串中数量为len(p)的字符，如果遍历到的字符属于列表，就将列表中的字符remove移除。如果遍历完后，列表为空，则证明此次遍历符合要求。否则进行下一次遍历。每次遍历都需要重新初始化列表。

缺点：遇到字符串超级长的时候，会超出时间限制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        res = []
        for i in range(len(s)):
            char_in_b = [c for c in p]
            num = len(char_in_b)
            for j in range(i,i+num):
                if j > len(s)-1:
                    break
                if s[j] in char_in_b:
                    char_in_b.remove(s[j])
                else:
                    break
            if char_in_b == []:
                res.append(i)
        return res

官方题解

初始化滑动窗口

依次在s和p中初始化滑动窗口，并且初始化26个字母的数组用来统计两个窗口中出现的字母次数。

特殊情况

首先考虑特殊情况，当p字符串比s字符串长，肯定不存在，返回空列表结果。

比较初始窗口

再比较两个初始化滑动窗口中的字母统计，是否相等，相等就添加一个初始化索引0。

开始滑动

开始滑动，滑动次数为len_s - len_p，s[i]对应的是左边待剔除的字母，需要-1；s[i+len(p)]对应的是右边待进入的字母，需要+1。每次滑动，需要比较字母统计是否相等，如果相等，结果需要添加i+1，因为滑动后的起始索引加1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        res = []
        # 特殊情况
        len_s = len(s)
        len_p = len(p)
        if len_p > len_s:
            return []
        # 初始化窗口
        s_count = [0] * 26
        p_count = [0] * 26
        # 比较初始化窗口中的内容
        for i in range(len_p):
            s_count[ord(s[i]) - 97] += 1
            p_count[ord(p[i]) - 97] += 1
        if s_count == p_count:
            res.append(0)
        # 逐个滑动窗口
        for i in range(len_s - len_p):
            s_count[ord(s[i]) - 97] -= 1
            s_count[ord(s[i+len_p]) - 97] += 1
            if s_count == p_count:
                res.append(i+1)           
        return res

知识点

根据字母获取对应字母表的索引

'a' 的 Unicode 码点值是 97 (ord('a') == 97)

1
ord(char) - 97

滑动

滑动次数是两个字符串的长度差，当前for循环其实是滑动前的状态，因为 i 从0开始的。

1
2
3
4
5
for i in range(len_s - len_p):
    s_count[ord(s[i]) - 97] -= 1
    s_count[ord(s[i+len_p]) - 97] += 1
    if s_count == p_count:
    res.append(i+1)