为什么我的代码不接受这些测试用例。 （字符串排列）

Question

类解决方案{

public static final Set<String> set = new HashSet<>();
public static void permutations(String str , String ans){
    //abc //""

    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) {
    permutations(s1 , "");

    for(String s : set){
        if(s2.contains(s)){
            return true;
        } 
    }

    return false;
    
}

}

上面的代码不接受测试用例： s1 = “abc” s2 = “ccccbbbbbaaaa”

正确的答案是假的，但我的代码返回真，但我不知道它发生了。

我创建了一个排列方法，它生成 s1 的所有可能排列并将所有排列存储在 HashSet 中，然后 CheckInclusion 方法检查 s2 是否包含 s1 的任何排列。

Answer 1

问题不在于您提到的具体测试用例，而在于您的实现不纯粹。它会改变一个静态字段，并在调用

checkInclusion

时默默地假设它是空的。但当使用多个不同的输入多次调用

checkInclusion

时，情况并非如此。因此，在对

checkInclusion

进行一些调用之后，该字段中将会有已经存在的条目，并且恰好是

s2

的子字符串，从而产生潜在的误报。

最短的解决方法是在函数顶部添加此语句，就在调用

permutation

之前：

set.clear();

现在您将得到预期的结果。但是您会遇到一个不同的问题：尽管您的算法返回正确的结果，但效率不高。对于较大的输入，将花费太多的时间和内存。例如，如果

s1

有 60 个字符，则要生成的排列数量比可观测宇宙中的原子还要多，所以不要指望你的

set

能够收集这些字符，更不用说它会花多长时间产生这些排列。

高效方法

需要一种完全不同的算法。尝试想出无需生成所有排列即可做到这一点的方法。

两个提示：

字母计数器

滑动窗口算法

如果按照这些提示你无法使其工作，这里有一个剧透解决方案：

    public boolean checkInclusion(String s1, String s2) {
         int n = s1.length();
         int m = s2.length();
         // Boundary case:
         if (m < n) {
             return false;
         }
         // Count how many we have of each character in s1
         int[] counter = new int[26]; // For each English lowercase letter
         for (var i = 0; i < n; i++) {
             counter[s1.charAt(i) - 'a']++;
         }
         // Count how many not-matching characters we have in the first n characters of s2
         int notMatched = 0;
         for (int right = 0; right < n; right++) {
             if (counter[s2.charAt(right) - 'a']-- == 0) {
                 // This is a nonmatching character
                 notMatched++;
             }
         }
         // Slide a window of size n over s2, doing the bookkeeping
         //   of how many we have of each in that window
         for (int right = n; right < m; right++) {
             if (notMatched == 0) {
                 return true;
             }
             if (++counter[s2.charAt(right - n) - 'a'] == 0) {
                 // This nonmatch slides OUT of the window
                 notMatched--;
             }
             if (counter[s2.charAt(right) - 'a']-- == 0) {
                 // This nonmatch slides INTO the window
                 notMatched++;
             }
         }
         return notMatched == 0;
     }