剑指 Offer II 014. 字符串中的变位词
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
示例 1： 输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba"). 示例 2： 输入: s1= "ab" s2 = "eidboaoo" 输出: False 提示： 1 <= s1.length, s2.length <= 104 s1 和 s2 仅包含小写字母 复制代码来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/MP…
思路
首先异位词的题目，一般都可以空间换时间去解决
所以我们可以使用哈希表去解决
但是题目中说到是小写字母，所以我们用固定大小的
26位数组去标记计数我们用
ab和cba来举例当出现
ab和abc这样的样例我们是最好解决的只要对应位置在数组中加一后再减一，就可以得出
ab是abc的子序列所以我们代码中第一次的判断就是做一个这样的情况
面对
ab和cba的情形，我们使用双指针去解决最开始是下面的情形
然后对应字符串
2的情况是下图所示
将
s1的字符串为滑动窗口的长度，每次进行扫描
class Solution { public boolean checkInclusion(String s1, String s2) { boolean flag = true; if (s2.length() < s1.length()) { return false; } int[] counts = new int[26]; for (int i = 0; i < s1.length(); i++) { counts[s1.charAt(i) - 'a']++; counts[s2.charAt(i) - 'a']--; } if (check(counts)) return true; for (int i = s1.length(); i < s2.length(); i++) { counts[s2.charAt(i) - 'a']--; counts[s2.charAt(i - s1.length()) - 'a']++; if (check(counts)) return true; } return false; } boolean check(int[] arr) { for (int i : arr) { if (i != 0) return false; } return true; } } 复制代码下一篇我们会去介绍，这道题的变种题，这篇主要使用双指针+标记法????
作者：xiaoff
链接：https://juejin.cn/post/7031333358562967566