LeetCode字符串排列问题：我的代码为何出现误判？

核心问题 #

你的代码里用了静态HashSetset，而LeetCode的测试环境是复用同一个Solution实例跑多个测试用例的。前一个测试用例执行完后，set里的排列不会被清空；到下一个测试用例时，这些旧数据会留在集合里，导致误判。

比如你说的这个测试用例，如果之前有个测试用例的s1是"aaa"，那set里会存"aaa"。当跑s1="abc"、s2="ccccbbbbaaaa"时，set里既有"abc"的排列，也有之前的"aaa"，而s2包含"aaa"，代码就错误返回true。但你本地只跑这一个测试用例，set里只有"abc"的排列，所以返回false——这就是本地和LeetCode结果不一致的原因。

修复方案 #

方案1：把静态集合改成实例成员变量+每次调用前清空 #

class Solution {
    private Set<String> set = new HashSet<>();

    public void permutations(String str , String ans){
        if(str.length() == 0){
            set.add(ans);
            return;
        }
        for(int i=0; i<str.length(); i++){
            String newStr = str.substring(0,i) + str.substring(i+1);
            permutations(newStr,ans + str.charAt(i));
        }
    }

    public boolean checkInclusion(String s1, String s2) {
        set.clear(); // 每次调用前清空集合，避免旧数据干扰
        permutations(s1 , "");
        for(String s : set){
            if(s2.contains(s)){
                return true;
            } 
        }
        return false;
    }
}

方案2：清空静态集合（不推荐，静态变量容易引发多实例问题） #

class Solution {
    public static final Set<String> set = new HashSet<>();

    public static void permutations(String str , String ans){
        if(str.length() == 0){
            set.add(ans);
            return;
        }
        for(int i=0; i<str.length(); i++){
            String newStr = str.substring(0,i) + str.substring(i+1);
            permutations(newStr,ans + str.charAt(i));
        }
    }

    public boolean checkInclusion(String s1, String s2) {
        set.clear(); // 每次调用前强制清空静态集合
        permutations(s1 , "");
        for(String s : set){
            if(s2.contains(s)){
                return true;
            } 
        }
        return false;
    }
}

额外优化提示 #

生成全排列的方法时间复杂度是O(n!)，当s1长度超过10左右就会超时。更高效的做法是用滑动窗口+字符计数：

• 统计s1中每个字符的出现次数，存在数组count1里
• 在s2上滑动一个长度等于s1长度的窗口，统计窗口内字符的出现次数count2
• 每次滑动窗口时更新count2，然后对比count1和count2是否完全一致，一致就返回true

这种方法时间复杂度是O(n)，能轻松处理大输入用例。

内容的提问来源于stack exchange，提问作者manav dubey