找出无序的anagramic对子串的数量

我想解决以下问题： 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 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分钟内

Answer 1

你可以看看这个链接。 这里解释得非常好。

我认为你存储所有的子串然后搜索anagram对，因为代码的空间复杂性非常大。 所以你可以改进它。 您还可以通过在它们不匹配的第一个点返回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< 

Answer 2

提前终止。 您可以使用HashMap，键是长度，值是相同长度的子串列表。 存储子字符串并仅检查“值”内的元素。 虽然如果长度不同，您可能认为它与提前终止的工作方式相同，但它会产生影响并且不会提前终止问题。

 import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int x=sc.nextInt(); for(int k=0; k> sub= getSub(str1); int counter=0; for(int t=1; t<=str1.length(); t++){ ArrayList subsl= sub.get(t); for(int i=0; i> getSub(String str1){ HashMap> ret= new HashMap>(); for(int i=0; i x= new ArrayList(); x.add(str1.substring(i, j+1)); ret.put(str1.substring(i, j+1).length(), x); } else ret.get(str1.substring(i, j+1).length()).add(str1.substring(i, j+1)); } } return ret; } public static boolean isAnagram(String a1, String a2){ int count1[]= new int[26]; int count2[]= new int[26]; if(a1.length()!=a2.length()) return false; for(int i=0; i 

如果你想让它更快，那么更改HashMap以包含一个具有所有26个字母的计数的对象。 这显然需要更多的记忆，所以你可以得到一些中间长度的东西，并说出字母a，b，c（或3个这样的字母）的数量。 为了使检查有效，使用位操作来编码所有这些（长度，a的计数，b的计数和c的计数）。 虽然注意不要超过Integer的位数。

Answer 3

尝试这个。 我在这里做的是将字符串分成两个子串并检查第二个字符串中的所有第一个字符串。

例如：abba

1st substring = a;

第二个子串= bba

现在检查bba中a的所有anagramic对

 import java.util.*; public class SherlockAndAnagrams{ public static void main(String[] args) { Scanner sc=new Scanner(System.in); int t=Integer.parseInt(sc.nextLine()); while(t-->0){ String s=sc.nextLine(); int count=0; for(int i=0;i < s.length();i++){ for(int k=i+1;k < s.length();k++){ int num=anagram(s.substring(i,k),s.substring(i+1),s.substring(i,k).length()); count=count+num; } } System.out.println(count); } } static int anagram(String s1,String s2,int len){ int count = 0; char[] c1=s1.toCharArray(); Arrays.sort(c1); String ss1=new String(c1); int length=s2.length(); for(int i=0;i 

}