LeetCode字符串排列子串问题：代码未通过指定测试用例的逻辑排查

问题描述 #

给定两个字符串s1和s2，如果s2包含s1的任意排列作为子串，返回true，否则返回false。

你的代码问题 #

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        do
        {   
            if(s2.find(s1)<s2.length())
            {
                return true;
            }
        }while(next_permutation(s1.begin(),s1.end()));
        return false;
    }
};

核心错误 #

1. 漏掉字典序更小的排列：next_permutation仅生成字典序大于当前字符串的排列。如果初始s1不是字典序最小的排列，所有比它小的排列都会被遗漏。比如你给出的测试用例：

   • s1 = "abcdxabcde"，而s2中的目标子串"abcdeabcdx"字典序小于初始s1，循环不会生成该排列，自然无法匹配返回false。

2. 时间复杂度爆炸：当s1长度为n时，全排列数量是n!，n=10时就有360万次循环，n=15时达到1e12量级，LeetCode测试用例会直接超时。

正确解法：滑动窗口+字符计数 #

判断两个字符串是否为排列的本质是字符出现频率完全相同，无需生成所有排列。用滑动窗口可高效验证：

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n1 = s1.size(), n2 = s2.size();
        if (n1 > n2) return false;
        
        vector<int> cnt1(26, 0), cnt2(26, 0);
        // 初始化窗口与s1的字符计数
        for (int i = 0; i < n1; ++i) {
            cnt1[s1[i] - 'a']++;
            cnt2[s2[i] - 'a']++;
        }
        if (cnt1 == cnt2) return true;
        
        // 滑动窗口更新计数
        for (int i = n1; i < n2; ++i) {
            cnt2[s2[i] - 'a']++;
            cnt2[s2[i - n1] - 'a']--;
            if (cnt1 == cnt2) return true;
        }
        return false;
    }
};

优化版本（减少比较次数） #

上述解法每次比较两个数组（O(26)时间），可维护diff变量记录差异字符数，进一步优化性能：

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n1 = s1.size(), n2 = s2.size();
        if (n1 > n2) return false;
        
        vector<int> cnt(26, 0);
        int diff = 0;
        for (int i = 0; i < n1; ++i) {
            cnt[s1[i] - 'a']++;
            cnt[s2[i] - 'a']--;
        }
        // 统计初始差异字符数
        for (int num : cnt) {
            if (num != 0) diff++;
        }
        if (diff == 0) return true;
        
        for (int i = n1; i < n2; ++i) {
            // 移除窗口左端字符
            char c1 = s2[i - n1];
            if (cnt[c1 - 'a'] == -1) diff--;
            else if (cnt[c1 - 'a'] == 0) diff++;
            cnt[c1 - 'a']++;
            
            // 加入窗口右端字符
            char c2 = s2[i];
            if (cnt[c2 - 'a'] == 1) diff--;
            else if (cnt[c2 - 'a'] == 0) diff++;
            cnt[c2 - 'a']--;
            
            if (diff == 0) return true;
        }
        return false;
    }
};

该优化版本时间复杂度为O(n2)，空间复杂度O(1)（数组大小固定为26），完全满足LeetCode性能要求。

内容的提问来源于stack exchange，提问作者Debarati Dutta Roy