Medium

题目描述

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = "ab", s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba")。

示例 2：

输入：s1 = "ab", s2 = "eidboaoo"
输出：false

提示：

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

解题思路

解题思路：

这道题要求判断 s2 是否包含 s1 的任意排列作为子串。关键洞察是：两个字符串互为排列当且仅当它们包含相同的字符且每个字符出现次数相同。

主要解法：

  1. 滑动窗口 + 字符频次统计（推荐）：使用长度为 s1.length 的滑动窗口在 s2 上移动，维护窗口内字符的频次统计，与 s1 的频次统计比较。

  2. 暴力解法：枚举 s2 中所有长度为 s1.length 的子串，逐一检查是否为 s1 的排列，时间复杂度较高。

滑动窗口实现细节：

  • 使用数组或哈希表记录 s1 和当前窗口的字符频次
  • 初始化窗口为 s2 的前 s1.length 个字符
  • 窗口向右滑动时，移除左端字符，添加右端字符
  • 每次移动后比较两个频次数组是否相等

这种方法避免了重复计算，大大提升了效率。使用数组存储频次比哈希表更快，因为只有26个小写字母。

代码实现

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if (s1.length() > s2.length()) return false;
        
        vector<int> s1Count(26, 0), s2Count(26, 0);
        
        // Count frequencies in s1 and first window of s2
        for (int i = 0; i < s1.length(); i++) {
            s1Count[s1[i] - 'a']++;
            s2Count[s2[i] - 'a']++;
        }
        
        // Check if first window matches
        if (s1Count == s2Count) return true;
        
        // Slide the window
        for (int i = s1.length(); i < s2.length(); i++) {
            // Add new character
            s2Count[s2[i] - 'a']++;
            // Remove old character
            s2Count[s2[i - s1.length()] - 'a']--;
            
            if (s1Count == s2Count) return true;
        }
        
        return false;
    }
};

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        
        s1_count = [0] * 26
        s2_count = [0] * 26
        
        # Count frequencies in s1 and first window of s2
        for i in range(len(s1)):
            s1_count[ord(s1[i]) - ord('a')] += 1
            s2_count[ord(s2[i]) - ord('a')] += 1
        
        # Check if first window matches
        if s1_count == s2_count:
            return True
        
        # Slide the window
        for i in range(len(s1), len(s2)):
            # Add new character
            s2_count[ord(s2[i]) - ord('a')] += 1
            # Remove old character
            s2_count[ord(s2[i - len(s1)]) - ord('a')] -= 1
            
            if s1_count == s2_count:
                return True
        
        return False

public class Solution {
    public bool CheckInclusion(string s1, string s2) {
        if (s1.Length > s2.Length) return false;
        
        int[] s1Count = new int[26];
        int[] s2Count = new int[26];
        
        // Count frequencies in s1 and first window of s2
        for (int i = 0; i < s1.Length; i++) {
            s1Count[s1[i] - 'a']++;
            s2Count[s2[i] - 'a']++;
        }
        
        // Check if first window matches
        if (AreEqual(s1Count, s2Count)) return true;
        
        // Slide the window
        for (int i = s1.Length; i < s2.Length; i++) {
            // Add new character
            s2Count[s2[i] - 'a']++;
            // Remove old character
            s2Count[s2[i - s1.Length] - 'a']--;
            
            if (AreEqual(s1Count, s2Count)) return true;
        }
        
        return false;
    }
    
    private bool AreEqual(int[] arr1, int[] arr2) {
        for (int i = 0; i < 26; i++) {
            if (arr1[i] != arr2[i]) return false;
        }
        return true;
    }
}

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function(s1, s2) {
    if (s1.length > s2.length) return false;
    
    const s1Count = new Array(26).fill(0);
    const s2Count = new Array(26).fill(0);
    
    // Count frequencies in s1 and first window of s2
    for (let i = 0; i < s1.length; i++) {
        s1Count[s1.charCodeAt(i) - 97]++;
        s2Count[s2.charCodeAt(i) - 97]++;
    }
    
    // Check if first window matches
    if (arraysEqual(s1Count, s2Count)) return true;
    
    // Slide the window
    for (let i = s1.length; i < s2.length; i++) {
        // Add new character
        s2Count[s2.charCodeAt(i) - 97]++;
        // Remove old character
        s2Count[s2.charCodeAt(i - s1.length) - 97]--;
        
        if (arraysEqual(s1Count, s2Count)) return true;
    }
    
    return false;
};

function arraysEqual(arr1, arr2) {
    for (let i = 0; i < 26; i++) {
        if (arr1[i] !== arr2[i]) return false;
    }
    return true;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大O表示法说明
时间复杂度O(n)其中 n 是 s2 的长度，需要遍历 s2 一次，每次比较字符频次数组需要 O(26) = O(1)
空间复杂度O(1)只使用了两个长度为 26 的数组存储字符频次，空间使用量为常数

相关题目