滑动窗口巧解字符串异位词

LeetCode438给定两个字符串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 的异位词。Python解法滑动窗口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 res # 26个小写字母计数 target [0] * 26 window [0] * 26 # 统计p的字符 for c in p: target[ord(c) - ord(a)] 1 # 初始化第一个窗口 for i in range(len_p): window[ord(s[i]) - ord(a)] 1 # 判断第一个窗口 if window target: res.append(0) # 滑动窗口 for right in range(len_p, len_s): # 移除左边滑出字符 left_out s[right - len_p] window[ord(left_out) - ord(a)] - 1 # 加入右边新字符 new_in s[right] window[ord(new_in) - ord(a)] 1 # 匹配则记录起点 if window target: res.append(right - len_p 1) return resJava解法滑动窗口class Solution { public ListInteger findAnagrams(String s, String p) { ListInteger res new ArrayList(); int lenS s.length(); int lenP p.length(); if(lenP lenS) return res; int[] target new int[26]; int[] window new int[26]; for(char c : p.toCharArray()){ target[c - a]; } // 初始化窗口 for(int i 0; i lenP; i){ window[s.charAt(i) - a]; } if(check(target, window)) res.add(0); // 滑动 for(int r lenP; r lenS; r){ char out s.charAt(r - lenP); window[out - a]--; char in s.charAt(r); window[in - a]; if(check(target, window)){ res.add(r - lenP 1); } } return res; } // 判断两个计数数组是否相等 boolean check(int[] a, int[] b){ for(int i 0; i 26; i){ if(a[i] ! b[i]) return false; } return true; } }C解法滑动窗口class Solution { public: vectorint findAnagrams(string s, string p) { vectorint res; int lenS s.size(); int lenP p.size(); if(lenP lenS) return res; vectorint target(26, 0), window(26, 0); for(char c : p) target[c - a]; for(int i 0; i lenP; i) window[s[i] - a]; if(target window) res.push_back(0); for(int r lenP; r lenS; r){ char out s[r - lenP]; window[out - a]--; char in s[r]; window[in - a]; if(target window) res.push_back(r - lenP 1); } return res; } };解释核心语言# 移除左边滑出字符 left_out s[right - len_p] window[ord(left_out) - ord(a)] - 1 # 加入右边新字符 new_in s[right] window[ord(new_in) - ord(a)] 11、核心前提窗口固定长度 len_pp 字符串长度 窗口区间[right - len_p 1 , right]每次右指针right右移一格窗口整体向右挪 1 位 最左侧旧字符要踢出窗口新的 right 字符要加入窗口。2、left_out s [right - len_p] 解释举例子len_p3right3窗口原本 0,1,2右移后 1,2,3要删掉下标3-30right4窗口原本 1,2,3右移后 2,3,4要删掉下标4-31公式right - len_p永远等于本轮滑出窗口的旧字符下标。3、window[ord(left_out) - ord(a)] - 1ord(c)-ord(a)把字母转为 0~25 数组下标a0,b1...z25window 数组存当前窗口每个字母出现次数旧字符离开窗口对应字母计数减 14、new_in s[right]right 是窗口新右边界这个字符刚进入滑动窗口需要计入统计。5、window[ord(new_in) - ord(a)] 1新字符加入窗口对应字母计数 1。分析原理一、滑动窗口原理固定 / 动态窗口区间只用增减进出窗口的元素更新统计量避免重复遍历区间时间 O (n)。两类定长窗口窗口长度固定438 字母异位词变长窗口左右指针伸缩无重复最长子串、最小覆盖子串二、适用题型定长窗口求固定长度子串满足条件、异位词、固定区间最值变长窗口子串和大于 / 小于目标含指定字符 / 无重复字符的最长 / 最短子串特征连续子数组 / 子字符串可通过区间进出快速更新计数、和、频次