题目描述

字符串中的变位词
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
示例 1:

  1. 输入: s1 = "ab" s2 = "eidbaooo"
  2. 输出: True
  3. 解释: s2 包含 s1 的排列之一 ("ba").

示例 2:

  1. 输入: s1= "ab" s2 = "eidboaoo"
  2. 输出: False

提示：

  • 1 <= s1.length, s2.length <= 104
  • s1 和 s2 仅包含小写字母

    解题思路

    滑动窗口
    一个定长字符串，顺序遍历比对一遍即可，一个关键问题就是如何快速，低占用的比对两个串是否字符一样。
    我最先想到的就是用hashMap，两个HashMap判断键值对是否一样。
    思路我觉得没问题的，问题就出在用了HashMap，太消耗资源了。
    image.png
    官方题解中则直接用数组就可以解决，对啊，小写字母对应了ASCII码啊，那就可以用数组很方便的确定index，而不用hashMap了

    实现代码

    1. public boolean checkInclusion(String s1,String s2){
    2. int n = s1.length(), m = s2.length();
    3. if (n > m) {
    4.   return false;
    5. }
    6. int[] cnt1 = new int[26];
    7. int[] cnt2 = new int[26];
    8. for (int i = 0; i < n; ++i) {
    9.   ++cnt1[s1.charAt(i) - 'a'];
    10.   ++cnt2[s2.charAt(i) - 'a'];
    11. }
    12. if (Arrays.equals(cnt1, cnt2)) {
    13.   return true;
    14. }
    15. for (int i = n; i < m; ++i) {
    16.   ++cnt2[s2.charAt(i) - 'a'];
    17.   --cnt2[s2.charAt(i - n) - 'a'];
    18.   if (Arrays.equals(cnt1, cnt2)) {
    19.     return true;
    20.   }
    21. }
    22. return false;
    23. }

    时间及空间复杂度分析

时间复杂度：O(n+m+∣Σ∣)，其中 nn 是字符串 s1的长度，mm 是字符串 s2的长度，|Σ| 是字符集，这道题中的字符集是小写字母，|Σ|=26。
空间复杂度：O(|Σ|)。

拓展思路

双指针