0567. Permutation in String =========================== 题目信息 -------- :题号: 0567 :难度: Medium :主题: 小写字符串、排列、连续子串、字符频次 :原题: `LeetCode 0567 `_ :重点: s2 必须包含一个长度等于 s1 的连续窗口、窗口字符频次与 s1 完全相同、字符顺序可以不同 题目重述 -------- 给定两个只含小写英文字母的字符串 ``s1`` 和 ``s2``,判断 ``s2`` 是否包含 ``s1`` 的某个排列作为连续子串。 也就是说,需要在 ``s2`` 中找到一个长度恰好等于 ``s1.length`` 的连续区间,使其中每个字符的出现次数与 ``s1`` 完全相同。不能从 ``s2`` 中跳过字符来组成非连续子序列。 自建示例 -------- 存在乱序连续窗口: .. code-block:: text 输入:s1 = "abc",s2 = "zzcabx" 输出:true 解释:s2 中的连续子串 "cab" 与 s1 含有相同字符及次数,是 s1 的一个排列。 字符存在但不连续: .. code-block:: text 输入:s1 = "xy",s2 = "axby" 输出:false 解释:x 和 y 都存在,但没有长度为 2 的连续子串同时包含它们。 固定窗口比较字符频次 -------------------- 排列只改变顺序,不改变字符频次,因此在 ``s2`` 上维护长度为 ``s1.size()`` 的滑动窗口。右端加入一个字符、窗口超长时移出左端,并维护两组 26 个字母的频次数组;当所有频次差为零时,窗口就是一个排列。 C++ 实现 -------- .. code-block:: cpp class Solution { public: bool checkInclusion(std::string s1, std::string s2) { if (s1.size() > s2.size()) return false; std::array need{}; std::array window{}; for (char character : s1) ++need[character - 'a']; int different = 0; for (int i = 0; i < 26; ++i) { if (need[i] != window[i]) ++different; } auto change = [&](int id, int delta) { if (window[id] == need[id]) ++different; window[id] += delta; if (window[id] == need[id]) --different; }; for (int right = 0; right < static_cast(s2.size()); ++right) { change(s2[right] - 'a', 1); if (right >= static_cast(s1.size())) { int left = right - static_cast(s1.size()); change(s2[left] - 'a', -1); } if (different == 0) return true; } return false; } }; 代码分析 -------- ``different`` 只在某个字母频次从相等变为不等或反向变化时更新,窗口长度达到目标后,所有频次相等与存在排列完全等价。时间复杂度为 ``O(|s1|+|s2|)``,额外空间复杂度为 ``O(1)``。