13. 判断一个字符串的排列是否是另一个字符串的子串。

PangHu大约 3 分钟

要判断一个字符串的排列是否是另一个字符串的子串，可以使用滑动窗口（Sliding Window）和哈希表（或数组）的方法。该方法的思路是：

使用一个固定长度的滑动窗口在目标字符串 s2 上滑动，窗口的长度等于字符串 s1 的长度。
在每次滑动时，检查窗口内的子串是否是字符串 s1 的某个排列。
判断方法可以通过比较滑动窗口内字符频率与字符串 s1 的字符频率是否相同来实现。

一、具体实现思路

首先，检查 s1 的字符频率。
在 s2 上使用一个与 s1 长度相同的滑动窗口。
对每个滑动窗口，计算窗口内的字符频率，并与 s1 的字符频率进行比较。
如果匹配，则说明 s1 的一个排列是 s2 的一个子串。

二、Java 代码实现

import java.util.Arrays;

public class PermutationInSubstring {
    
    public static boolean checkInclusion(String s1, String s2) {
        int[] s1Count = new int[26];
        int[] s2Count = new int[26];
        
        // 如果 s1 长度大于 s2，直接返回 false
        if (s1.length() > s2.length()) {
            return false;
        }
        
        // 计算 s1 的字符频率
        for (int i = 0; i < s1.length(); i++) {
            s1Count[s1.charAt(i) - 'a']++;
            s2Count[s2.charAt(i) - 'a']++;
        }
        
        // 滑动窗口：窗口的初始范围是 s2[0..s1.length()-1]
        for (int i = 0; i < s2.length() - s1.length(); i++) {
            // 如果当前窗口字符频率与 s1 相同，则返回 true
            if (Arrays.equals(s1Count, s2Count)) {
                return true;
            }
            // 将窗口右移：移除左边字符，加入右边字符
            s2Count[s2.charAt(i) - 'a']--;
            s2Count[s2.charAt(i + s1.length()) - 'a']++;
        }
        
        // 检查最后一个窗口
        return Arrays.equals(s1Count, s2Count);
    }

    public static void main(String[] args) {
        String s1 = "ab";
        String s2 = "eidbaooo";

        boolean result = checkInclusion(s1, s2);
        System.out.println("Does s2 contain a permutation of s1? " + result);
    }
}

三、代码详解

字符频率数组：
- s1Count 和 s2Count 是长度为 26 的数组，用于存储各个字符在字符串中的出现频率。由于题目给定的是小写字母，这里用数组下标 0 到 25 对应字符 'a' 到 'z'。
初始窗口：
- 初始化时，s1Count 数组存储字符串 s1 中每个字符的频率，同时计算 s2 的前 s1.length() 个字符的频率，存储在 s2Count 中。
滑动窗口：
- 在 s2 上的滑动窗口逐步右移。每次右移时，更新窗口字符频率，即减少左边界字符的频率，增加右边界字符的频率。
- 在每次窗口更新后，比较 s1Count 和 s2Count 是否相同。如果相同，说明 s1 的一个排列是 s2 的一个子串。
边界条件：
- 在最后一次比较时，窗口已经覆盖了字符串 s2 的末尾部分，因此需要在循环结束后进行一次最终的比较。

四、时间复杂度与空间复杂度

时间复杂度：O(n)，其中 n 是字符串 s2 的长度。计算字符频率和滑动窗口操作的时间复杂度都是 O(n)。
空间复杂度：O(1)，只使用了固定大小的额外空间（两个长度为 26 的数组）。

五、总结

该方法使用了滑动窗口和字符频率计数的技巧，能够有效地判断一个字符串的排列是否是另一个字符串的子串。通过将时间复杂度降低到 O(n)，它能够在实际应用中处理较大规模的数据。