查找无序字谜对子串的数量

我正在尝试解决以下问题：https://www.hackerrank.com/challenges/sherlock-and-anagrams https://www.hackerrank.com/challenges/sherlock-and-anagrams

这是我的代码

import java.util.*;
public class Solution {

public static boolean check(String s1,String s2)
{

    int [] count1 = new int[26];
    for( int i = 0; i < s1.length(); i++ )
    {
        char ch1 = s1.charAt(i);
        count1[ch1-'a']++;
    }

    int [] count2 = new int[26];
    for( int i = 0; i < s2.length(); i++ )
    {
        char ch2 = s2.charAt(i);
        count2[ch2-'a']++;
    }

    int count =0;
    for(int j=0;j<26;j++)
    {
        count = count + Math.abs(count1[j]-count2[j]);
    }

    if(count ==0)
            return true;
    else return false;
}
public static void main(String[] args) {

    String s,sub;
    int i,c,len;
    List<String> all = new ArrayList<>();

    Scanner in = new Scanner(System.in);
    int t = Integer.parseInt(in.nextLine());

      while((t--)>0)
    {
          s  = in.nextLine();
          len = s.length();   
       for( c = 0 ; c < len ; c++ )
       {
           for( i = 1 ; i <= len - c ; i++ )
          {
             sub = s.substring(c, c+i);
            all.add(sub);
          }
       }

      String[] arr = new String[all.size()];
      for( i = 0; i < all.size(); i++) 
              arr[i] = all.get(i);

          int l=0;
          for (int m=0;m<arr.length;m++)
          {
              for(int n=m+1;n<arr.length;n++)
               {
                  if(check(arr[m],arr[n]))
                         l++;
              }
          }

          System.out.println(l);all.clear();
    }

}
}

我的代码适用于少数具有小字符串的测试用例，但如果字符串大小太大则无法工作

输入样本

5
ifailugtyovhdfuhdouarjsnrbfpvmupwjjjfiwneogwnoegnoegneognoewhrlkpekxxnebfrwibylcvkfealgonjkzw
gffryqktmwocejbrexfidpjfgrrkpowoxwggxaknmltjcpazgtnakcfbveieivoenwvpnoevvneocogzatyskqjyorcftw
uqlzvuzgkwhkkrrfpwarkckansgabfclzgnumdrojexnofeqjnqnxwidhbvbenevun9evnnv9euxxhfwargwkikjq
sygjxynvofnvirarcoacwnhxyqlrviikfuiuotifznqmzpjrxycnqkeibvibvewioebvitkryutpqvbgbgthfges
mkenscyiamnwlpxytkndjsygifmqlqibxxqlauxamfviftquntvkwppxrzuncyenavebiobeviobeiobeibvcfivtigv

我的输出

4s : Terminated due to timeout

有没有更好的方法来解决它或更改现有代码以使执行时间在 4 分钟内

您可以查看this http://www.geeksforgeeks.org/anagram-substring-search-search-permutations/关联。这里解释得很好。

我认为您正在存储所有子字符串，然后搜索字谜对，因为您的代码的空间复杂度非常高。所以你可以改进这一点。您还可以减少您的操作次数check通过返回函数false在他们不匹配的第一点。

我已经用c++实现了上述问题。这是我的代码：

#define MAX 26
bool isAnagram(int *count1, int *count2) {
    for(int i = 0; i < MAX; i++) {
        if(count1[i] != count2[i])
            return false;
    }
    return true;
}

int findPair(string str, int start, char *tmp, int n) {
    int len = str.length();
    if(strlen(tmp) > len-start) {
        return 0;
    }

    int *count1 = new int[MAX];
    int *count2 = new int[MAX];
    int cnt = 0;
    int i;
    for(i = 0; i < MAX; i++) {
        count1[i] = 0; 
        count2[i] = 0;
    }

    for(i = 0; i < n && (start+i) < len; i++) {
        count1[tmp[i]-'a']++;
        count2[str[start+i]-'a']++;
    }

    int j;
    for(j = start + i; j < len; j++) {
        if(isAnagram(count1, count2)) {
            cnt++;
        }
        count2[str[start]-'a']--;
        count2[str[j]-'a']++;
        start++;
    }
    if(j == len) {
        if(isAnagram(count1, count2)) {
            cnt++;
        }
    }

    delete []count1;
    delete []count2;

    return cnt;
}

int countPairs(string str) {
    int n = str.length();
    if(n < 2) {
        return 0;
    }

    int cnt = 0;
    char *tmp = new char[n];
    for(int i = 0; i < n; i++) {
        int k = 0;
        for(int j = i; j < n; j++) {
            tmp[k] = str[j];
            tmp[k+1] = '\0';

            cnt += findPair(str, i+1, tmp, k+1);
            k++;
        }
    }
    delete []tmp;
    return cnt;
}

int main() {
    int t;
    cin>>t;

    while(t--) {
        string str;
        cin>>str;
        cout<<countPairs(str)<<endl;
    }

    return 0;
}