字符串排列检测 checkInclusionLeetCode 567 三种解法与滑动窗口深入剖析【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南以仓库文档 permutation-string.md 为骨架系统讲解 LeetCode 567「字符串的排列」Permutation in String一题如何在s2中判断是否存在s1的某个排列作为连续子串。全文覆盖暴力枚举、哈希表频次统计、固定窗口滑动三条完整解题路线并结合本仓库多语言源码如 python/0567-permutation-in-string.py、cpp/0567-permutation-in-string.cpp、java/0567-permutation-in-string.java印证实现细节。读完你将掌握排序比较 → 频次匹配 → 滑动窗口维护 matches 计数的完整递进思路并能在面试或工程场景中直接写出 O(n) 时间、O(1) 空间的解法。前置知识Prerequisites在动手实现前建议先熟悉以下四个基础能力它们是本题三种解法各自的地基哈希表 / 频次统计Hash Tables / Frequency Counting统计字符出现次数用于比较子串与s1是否包含相同字符集合滑动窗口Sliding Window Technique在不重建计数的情况下高效检查固定长度子串是最终 O(n) 解法的核心字符串处理String Manipulation子串提取与字符比较的常规操作排序Sorting暴力解法中通过排序后的字符串比较来判断是否为排列。仓库提示本题的解题提示与复杂度建议可参考 hints/permutation-string.md其中明确建议目标解法应达到O(n)时间与O(1)空间并提示可以用判断 anagram 的字符频次思路。1. 暴力枚举Brute Force核心直觉Intuition暴力法的思路最直白排列 字符完全相同、顺序任意。因此我们先把s1排序一次得到基准串然后枚举s2中每一个可能的子串把子串也排序后与基准串比较。若两者相等说明子串与s1包含完全相同的字符集合即找到了s1的一个排列。这种方法简单易懂但代价高昂——它枚举了所有子串并对每一个子串都执行一次排序。算法步骤Algorithm对s1排序得到可比较的基准串遍历s2的每一个起始下标i对每个i再遍历所有结束下标j ≥ i取出子串s2[i : j1]对子串排序并与排序后的s1比较相等则返回true若全部枚举完毕仍无匹配返回false。多语言实现class Solution: def checkInclusion(self, s1: str, s2: str) - bool: s1 sorted(s1) for i in range(len(s2)): for j in range(i, len(s2)): subStr s2[i : j 1] subStr sorted(subStr) if subStr s1: return True return Falsepublic class Solution { public boolean checkInclusion(String s1, String s2) { char[] s1Arr s1.toCharArray(); Arrays.sort(s1Arr); String sortedS1 new String(s1Arr); for (int i 0; i s2.length(); i) { for (int j i; j s2.length(); j) { char[] subStrArr s2.substring(i, j 1).toCharArray(); Arrays.sort(subStrArr); String sortedSubStr new String(subStrArr); if (sortedSubStr.equals(sortedS1)) { return true; } } } return false; } }class Solution { public: bool checkInclusion(std::string s1, std::string s2) { sort(s1.begin(), s1.end()); for (int i 0; i s2.length(); i) { for (int j i; j s2.length(); j) { string subStr s2.substr(i, j - i 1); sort(subStr.begin(), subStr.end()); if (subStr s1) { return true; } } } return false; } };class Solution { /** * param {string} s1 * param {string} s2 * return {boolean} */ checkInclusion(s1, s2) { s1 s1.split().sort().join(); for (let i 0; i s2.length; i) { for (let j i; j s2.length; j) { let subStr s2 .slice(i, j 1) .split() .sort() .join(); if (subStr s1) { return true; } } } return false; } }func checkInclusion(s1 string, s2 string) bool { s1Sorted : []rune(s1) sort.Slice(s1Sorted, func(i, j int) bool { return s1Sorted[i] s1Sorted[j] }) s1 string(s1Sorted) for i : 0; i len(s2); i { for j : i; j len(s2); j { subStr : s2[i : j1] subStrSorted : []rune(subStr) sort.Slice(subStrSorted, func(a, b int) bool { return subStrSorted[a] subStrSorted[b] }) if string(subStrSorted) s1 { return true } } } return false }impl Solution { pub fn check_inclusion(s1: String, s2: String) - bool { let mut s1_sorted: Vecu8 s1.bytes().collect(); s1_sorted.sort(); let s2 s2.as_bytes(); for i in 0..s2.len() { for j in i..s2.len() { let mut sub: Vecu8 s2[i..j].to_vec(); sub.sort(); if sub s1_sorted { return true; } } } false } }复杂度分析时间复杂度$O(n^3 \log n)$两层循环枚举子串每个子串排序空间复杂度$O(n)$排序产生的临时数组。说明实际最坏开销取决于子串数量与每次排序的规模暴力法仅适合理解题意工程上不可接受。2. 哈希表频次匹配Hash Table核心直觉Intuition观察到一个关键事实任何合法的子串其各字符的出现频次必须与s1完全一致。于是我们不再排序而是先统计s1中每个字符的出现次数存入count1枚举s2的每个起始点边扩展子串边维护一张新的频次表count2一旦某个字符在count2中的次数超过count1的要求立即break——该子串已不可能成为排列当所有字符的计数都精确匹配cur need时即找到了合法排列。相比暴力法这种方法思路更干净但因为它对每个起始位置都要重新开始计数整体仍然偏慢。算法步骤Algorithm构建s1的频次表count1令need为s1中需要精确匹配的不同字符数即count1的大小对s2的每个起始下标i新建空表count2与匹配计数器cur 0让j从i向后扩展子串count2[s2[j]]自增若count2[s2[j]]超过count1的要求break放弃该起点若该字符计数恰好等于count1的要求cur加一若cur need返回true所有起点都尝试完毕仍无匹配返回false。多语言实现class Solution: def checkInclusion(self, s1: str, s2: str) - bool: count1 {} for c in s1: count1[c] 1 count1.get(c, 0) need len(count1) for i in range(len(s2)): count2, cur {}, 0 for j in range(i, len(s2)): count2[s2[j]] 1 count2.get(s2[j], 0) if count1.get(s2[j], 0) count2[s2[j]]: break if count1.get(s2[j], 0) count2[s2[j]]: cur 1 if cur need: return True return Falsepublic class Solution { public boolean checkInclusion(String s1, String s2) { MapCharacter, Integer count1 new HashMap(); for (char c : s1.toCharArray()) { count1.put(c, count1.getOrDefault(c, 0) 1); } int need count1.size(); for (int i 0; i s2.length(); i) { MapCharacter, Integer count2 new HashMap(); int cur 0; for (int j i; j s2.length(); j) { char c s2.charAt(j); count2.put(c, count2.getOrDefault(c, 0) 1); if (count1.getOrDefault(c, 0) count2.get(c)) { break; } if (count1.getOrDefault(c, 0) count2.get(c)) { cur; } if (cur need) { return true; } } } return false; } }class Solution { public: bool checkInclusion(string s1, string s2) { unordered_mapchar, int count1; for (char c : s1) { count1[c]; } int need count1.size(); for (int i 0; i s2.length(); i) { unordered_mapchar, int count2; int cur 0; for (int j i; j s2.length(); j) { char c s2[j]; count2[c]; if (count1[c] count2[c]) { break; } if (count1[c] count2[c]) { cur; } if (cur need) { return true; } } } return false; } };class Solution { /** * param {string} s1 * param {string} s2 * return {boolean} */ checkInclusion(s1, s2) { let count1 {}; for (let c of s1) { count1[c] (count1[c] || 0) 1; } let need Object.keys(count1).length; for (let i 0; i s2.length; i) { let count2 {}; let cur 0; for (let j i; j s2.length; j) { let c s2[j]; count2[c] (count2[c] || 0) 1; if ((count1[c] || 0) count2[c]) { break; } if ((count1[c] || 0) count2[c]) { cur; } if (cur need) { return true; } } } return false; } }func checkInclusion(s1 string, s2 string) bool { count1 : make(map[rune]int) for _, c : range s1 { count1[c] } need : len(count1) for i : 0; i len(s2); i { count2 : make(map[rune]int) cur : 0 for j : i; j len(s2); j { count2[rune(s2[j])] if count1[rune(s2[j])] count2[rune(s2[j])] { break } if count1[rune(s2[j])] count2[rune(s2[j])] { cur } if cur need { return true } } } return false }class Solution { fun checkInclusion(s1: String, s2: String): Boolean { val count1 HashMapChar, Int() for (c in s1) { count1[c] 1 count1.getOrDefault(c, 0) } val need count1.size for (i in s2.indices) { val count2 mutableMapOfChar, Int() var cur 0 for (j in i until s2.length) { count2[s2[j]] 1 count2.getOrDefault(s2[j], 0) if (count1.getOrDefault(s2[j], 0) count2[s2[j]]!!) { break } if (count1.getOrDefault(s2[j], 0) count2[s2[j]]!!) { cur } if (cur need) { return true } } } return false } }impl Solution { pub fn check_inclusion(s1: String, s2: String) - bool { let mut count1 HashMap::new(); for c in s1.bytes() { *count1.entry(c).or_insert(0) 1; } let need count1.len(); let s2 s2.as_bytes(); for i in 0..s2.len() { let mut count2 HashMap::new(); let mut cur 0; for j in i..s2.len() { let c s2[j]; *count2.entry(c).or_insert(0) 1; let c1 *count1.get(c).unwrap_or(0); let c2 *count2.get(c).unwrap_or(0); if c1 c2 { break; } if c1 c2 { cur 1; } if cur need { return true; } } } false } }复杂度分析时间复杂度$O(n \times m)$其中 $n$ 为s1长度、$m$ 为s2长度每个起点最多延伸 $m$ 次并受need约束提前终止空间复杂度$O(1)$因为字符表最多只有 26 个不同字符两张哈希表的规模是常数级。3. 滑动窗口Sliding Window——最优解核心直觉Intuitions1的任一排列必然具有与s1完全相同的字符频次。因此我们可以在s2上维护一个长度固定为len(s1)的窗口并维护两张频次数组一张记录s1的字符频次一张记录s2当前窗口内字符的频次。只要两张频次数组完全一致当前窗口就是一个合法排列。窗口向前滑动时我们只需要移除左边字符、加入右边字符来增量更新频次完全无需重建计数。这是本题最高效的解法。算法步骤Algorithm若s1比s2长直接返回false不可能存在排列子串构建频次数组s1的频次s2中第一个长度为len(s1)的窗口的频次统计两张数组在 26 个位置上有多少个位置计数一致记为matches从左到右滑动窗口每步先判断matches 26是则返回true加入新右字符并更新matches移除左字符并更新matches左指针右移循环结束后返回matches 26。源码级对照仓库实现仓库中的 python/0567-permutation-in-string.py 正是该滑动窗口方案的标准实现class Solution: def checkInclusion(self, s1: str, s2: str) - bool: if len(s1) len(s2): return False s1Count, s2Count [0] * 26, [0] * 26 for i in range(len(s1)): s1Count[ord(s1[i]) - ord(a)] 1 s2Count[ord(s2[i]) - ord(a)] 1 matches 0 for i in range(26): matches 1 if s1Count[i] s2Count[i] else 0 l 0 for r in range(len(s1), len(s2)): if matches 26: return True index ord(s2[r]) - ord(a) s2Count[index] 1 if s1Count[index] s2Count[index]: matches 1 elif s1Count[index] 1 s2Count[index]: matches - 1 index ord(s2[l]) - ord(a) s2Count[index] - 1 if s1Count[index] s2Count[index]: matches 1 elif s1Count[index] - 1 s2Count[index]: matches - 1 l 1 return matches 26matches 计数器的增量更新规则值得仔细推敲这也是全题最容易写错的地方加入右字符s2[r]后若s2Count[index]恰好等于s1Count[index]说明该位置从不匹配变为匹配matches 1若加入后s2Count[index]比s1Count[index]多 1即s1Count[index] 1 s2Count[index]说明该位置从匹配变为超配matches - 1移除左字符s2[l]时对称处理恰好相等则matches 1比目标少 1s1Count[index] - 1 s2Count[index]则matches - 1。仓库还提供了同思路的 TypeScript 实现 typescript/0567-permutation-in-string.ts使用charCodeAt(0) - a.charCodeAt(0)计算下标以及一个单数组差分实现cpp/0567-permutation-in-string.cpp// 摘自 cpp/0567-permutation-in-string.cpp // 用单个 count 数组做差分s1 字符 1窗口内字符 -1 // 当 count 数组全部为 0 时说明窗口与 s1 频次完全一致 vectorint count(26); for (int i 0; i m; i) { count[s1[i] - a]; count[s2[i] - a]--; } if (isPermutation(count)) return true; for (int i m; i n; i) { count[s2[i] - a]--; // 加入新右字符 count[s2[i - m] - a]; // 移除旧左字符 if (isPermutation(count)) return true; }该实现用差分归零代替双数组逐位比较isPermutation每次扫描 26 个位置判断是否全为 0语义等价且同样为 O(26) 常数开销。java/0567-permutation-in-string.java 则用Arrays.equals(freq, freq2)直接比较两张频次表同样是固定窗口 增量更新的思路。多语言实现class Solution: def checkInclusion(self, s1: str, s2: str) - bool: if len(s1) len(s2): return False s1Count, s2Count [0] * 26, [0] * 26 for i in range(len(s1)): s1Count[ord(s1[i]) - ord(a)] 1 s2Count[ord(s2[i]) - ord(a)] 1 matches 0 for i in range(26): matches (1 if s1Count[i] s2Count[i] else 0) l 0 for r in range(len(s1), len(s2)): if matches 26: return True index ord(s2[r]) - ord(a) s2Count[index] 1 if s1Count[index] s2Count[index]: matches 1 elif s1Count[index] 1 s2Count[index]: matches - 1 index ord(s2[l]) - ord(a) s2Count[index] - 1 if s1Count[index] s2Count[index]: matches 1 elif s1Count[index] - 1 s2Count[index]: matches - 1 l 1 return matches 26public class Solution { public boolean checkInclusion(String s1, String s2) { if (s1.length() s2.length()) { return false; } int[] s1Count new int[26]; int[] s2Count new int[26]; for (int i 0; i s1.length(); i) { s1Count[s1.charAt(i) - a]; s2Count[s2.charAt(i) - a]; } int matches 0; for (int i 0; i 26; i) { if (s1Count[i] s2Count[i]) { matches; } } int l 0; for (int r s1.length(); r s2.length(); r) { if (matches 26) { return true; } int index s2.charAt(r) - a; s2Count[index]; if (s1Count[index] s2Count[index]) { matches; } else if (s1Count[index] 1 s2Count[index]) { matches--; } index s2.charAt(l) - a; s2Count[index]--; if (s1Count[index] s2Count[index]) { matches; } else if (s1Count[index] - 1 s2Count[index]) { matches--; } l; } return matches 26; } }class Solution { public: bool checkInclusion(string s1, string s2) { if (s1.length() s2.length()) { return false; } vectorint s1Count(26, 0); vectorint s2Count(26, 0); for (int i 0; i s1.length(); i) { s1Count[s1[i] - a]; s2Count[s2[i] - a]; } int matches 0; for (int i 0; i 26; i) { if (s1Count[i] s2Count[i]) { matches; } } int l 0; for (int r s1.length(); r s2.length(); r) { if (matches 26) { return true; } int index s2[r] - a; s2Count[index]; if (s1Count[index] s2Count[index]) { matches; } else if (s1Count[index] 1 s2Count[index]) { matches--; } index s2[l] - a; s2Count[index]--; if (s1Count[index] s2Count[index]) { matches; } else if (s1Count[index] - 1 s2Count[index]) { matches--; } l; } return matches 26; } };class Solution { /** * param {string} s1 * param {string} s2 * return {boolean} */ checkInclusion(s1, s2) { if (s1.length s2.length) { return false; } let s1Count new Array(26).fill(0); let s2Count new Array(26).fill(0); for (let i 0; i s1.length; i) { s1Count[s1.charCodeAt(i) - 97]; s2Count[s2.charCodeAt(i) - 97]; } let matches 0; for (let i 0; i 26; i) { if (s1Count[i] s2Count[i]) { matches; } } let l 0; for (let r s1.length; r s2.length; r) { if (matches 26) { return true; } let index s2.charCodeAt(r) - 97; s2Count[index]; if (s1Count[index] s2Count[index]) { matches; } else if (s1Count[index] 1 s2Count[index]) { matches--; } index s2.charCodeAt(l) - 97; s2Count[index]--; if (s1Count[index] s2Count[index]) { matches; } else if (s1Count[index] - 1 s2Count[index]) { matches--; } l; } return matches 26; } }func checkInclusion(s1 string, s2 string) bool { if len(s1) len(s2) { return false } s1Count : make([]int, 26) s2Count : make([]int, 26) for i : 0; i len(s1); i { s1Count[s1[i]-a] s2Count[s2[i]-a] } matches : 0 for i : 0; i 26; i { if s1Count[i] s2Count[i] { matches } } l : 0 for r : len(s1); r len(s2); r { if matches 26 { return true } index : s2[r] - a s2Count[index] if s1Count[index] s2Count[index] { matches } else if s1Count[index]1 s2Count[index] { matches-- } index s2[l] - a s2Count[index]-- if s1Count[index] s2Count[index] { matches } else if s1Count[index]-1 s2Count[index] { matches-- } l } return matches 26 }class Solution { fun checkInclusion(s1: String, s2: String): Boolean { if (s1.length s2.length) return false val s1Count IntArray(26) val s2Count IntArray(26) for (i in s1.indices) { s1Count[s1[i] - a] s2Count[s2[i] - a] } var matches 0 for (i in 0 until 26) { if (s1Count[i] s2Count[i]) matches } var l 0 for (r in s1.length until s2.length) { if (matches 26) return true val index s2[r] - a s2Count[index] if (s1Count[index] s2Count[index]) { matches } else if (s1Count[index] 1 s2Count[index]) { matches-- } val leftIndex s2[l] - a s2Count[leftIndex]-- if (s1Count[leftIndex] s2Count[leftIndex]) { matches } else if (s1Count[leftIndex] - 1 s2Count[leftIndex]) { matches-- } l } return matches 26 } }class Solution { func checkInclusion(_ s1: String, _ s2: String) - Bool { if s1.count s2.count { return false } var s1Count Int var s2Count Int let aAscii Int(Character(a).asciiValue!) let s1Array Array(s1) let s2Array Array(s2) for i in 0..s1.count { s1Count[Int(s1Array[i].asciiValue!) - aAscii] 1 s2Count[Int(s2Array[i].asciiValue!) - aAscii] 1 } var matches 0 for i in 0..26 { if s1Count[i] s2Count[i] { matches 1 } } var l 0 for r in s1.count..s2.count { if matches 26 { return true } var index Int(s2Array[r].asciiValue!) - aAscii s2Count[index] 1 if s1Count[index] s2Count[index] { matches 1 } else if s1Count[index] 1 s2Count[index] { matches - 1 } index Int(s2Array[l].asciiValue!) - aAscii s2Count[index] - 1 if s1Count[index] s2Count[index] { matches 1 } else if s1Count[index] - 1 s2Count[index] { matches - 1 } l 1 } return matches 26 } }impl Solution { pub fn check_inclusion(s1: String, s2: String) - bool { let s1 s1.as_bytes(); let s2 s2.as_bytes(); if s1.len() s2.len() { return false; } let mut s1_count [0i32; 26]; let mut s2_count [0i32; 26]; for i in 0..s1.len() { s1_count[(s1[i] - ba) as usize] 1; s2_count[(s2[i] - ba) as usize] 1; } let mut matches 0; for i in 0..26 { if s1_count[i] s2_count[i] { matches 1; } } let mut l 0; for r in s1.len()..s2.len() { if matches 26 { return true; } let idx (s2[r] - ba) as usize; s2_count[idx] 1; if s1_count[idx] s2_count[idx] { matches 1; } else if s1_count[idx] 1 s2_count[idx] { matches - 1; } let idx (s2[l] - ba) as usize; s2_count[idx] - 1; if s1_count[idx] s2_count[idx] { matches 1; } else if s1_count[idx] - 1 s2_count[idx] { matches - 1; } l 1; } matches 26 } }复杂度分析时间复杂度$O(n)$其中 $n$ 为s2的长度窗口只完整滑动一遍matches的维护是 O(1)空间复杂度$O(1)$固定 26 长度的频次数组与输入规模无关。与 hints/permutation-string.md 中Recommended Time Space Complexity给出的O(n)时间、O(1)空间目标完全一致。三种解法复杂度对比解法时间复杂度空间复杂度适用场景暴力枚举排序比较$O(n^3 \log n)$$O(n)$仅用于理解题意哈希表频次匹配$O(n \times m)$$O(1)$无滑动窗口知识时的过渡方案滑动窗口$O(n)$$O(1)$面试与生产首选常见陷阱Common Pitfalls陷阱一进入前不检查长度如果s1比s2更长那么s1的任何排列都不可能成为s2的子串。漏掉这个前置判断不仅会做大量无谓计算在初始化滑动窗口直接用s1的长度去取s2的前缀时还可能触发越界或索引错误。因此第一行就应判断len(s1) len(s2)并返回false仓库各语言实现如 python/0567-permutation-in-string.py均包含该检查。陷阱二窗口尺寸错误滑动窗口的尺寸必须严格等于len(s1)。常见错误包括使用了可变尺寸的窗口或在加入新右字符时忘记移除最左侧字符。这两种情况都会破坏频次比较的前提导致结果错误。牢记每滑一步一进一出。陷阱三matches 计数器更新错误窗口滑动过程中更新频次时matches计数器的维护必须非常小心某字符从匹配变为不匹配时matches要减一从不匹配变为匹配时matches要加一这些条件里的 off-by-one把写成1/-1的比较或方向写反会让算法漏掉合法窗口或产生误报。建议对照本文第 3 节给出的加右、减左两段更新逻辑逐字符推演一遍例如以s1 ab、s2 eidbaooo为例窗口滑到ba时matches恰好达到 26即可彻底吃透这条最易出错的分支逻辑。延伸阅读本题的完整讲解骨架见 articles/permutation-string.md滑动窗口判断异位词的姊妹题返回所有起始下标见 articles/find-all-anagrams-in-a-string.md其思路与本题几乎完全一致区别仅在于收集下标列表而非返回布尔值多语言实现可对照 python/0567-permutation-in-string.py、java/0567-permutation-in-string.java、go/0567-permutation-in-string.go、swift/0567-permutation-in-string.swift、rust/0567-permutation-in-string.rs 等文件官方难度提示与分步 Hint 见 hints/permutation-string.md。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考