| 题目链接 | 438. 找到字符串中所有字母异位词 |
|---|---|
| 思路 | 滑动窗口 |
| 题解链接 | 官方题解 |
| 关键点 | 顺序比较；判断的状态量可以依此变更时应当使用“滑动窗口”的方式进行更新 |
| 时间复杂度 | \(O(m + (n-m)\times\sum)\) |
| 空间复杂度 | \(O(\sum)\) |
代码实现：
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
s_len = len(s)
p_len = len(p)
if s_len < p_len:
return []
answer = []
s_count = [0] * 26
p_count = [0] * 26
a_ord = ord('a')
for i in range(p_len):
s_count[ord(s[i]) - a_ord] += 1
p_count[ord(p[i]) - a_ord] += 1
if s_count == p_count:
answer.append(0)
for i in range(s_len - p_len):
s_count[ord(s[i]) - a_ord] -= 1
s_count[ord(s[i+p_len]) - a_ord] += 1
if s_count == p_count:
answer.append(i+1)
return answer
python-优化版本的滑动窗口
思路：维护“差异量” 时间复杂度：由$O(n+(n-m)\times\sum)$下降至$O(n+m+\sum)$class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
s_len = len(s)
p_len = len(p)
if s_len < p_len:
return []
answer = []
a_ord = ord('a')
ch_diff_count = [0] * 26
for i in range(p_len):
ch_diff_count[ord(s[i]) - a_ord] += 1
ch_diff_count[ord(p[i]) - a_ord] -= 1
diff = sum([
item != 0
for item in ch_diff_count
])
if diff == 0:
answer.append(0)
for i in range(s_len - p_len):
index = ord(s[i]) - a_ord
if ch_diff_count[index] == 1:
diff -= 1
elif ch_diff_count[index] == 0:
diff += 1
ch_diff_count[index] -= 1
index = ord(s[i+p_len]) - a_ord
if ch_diff_count[index] == -1:
diff -= 1
elif ch_diff_count[index] == 0:
diff += 1
ch_diff_count[index] += 1
if diff == 0:
answer.append(i+1)
return answer