找出子串的无序变位词对的数量

Question

我正在尝试解决以下问题： 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分钟以内

Answer 1

您可以查看 this link。这里解释的很好

我认为您正在存储所有子字符串，然后搜索变位词对，因为 space 您的代码非常复杂。所以你可以改进它。您还可以通过返回 false 来减少 check 函数中的操作次数在它们不匹配的第一个点。

我已经用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] = '[=10=]';

            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;
}

Answer 2

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

对于ex:abba

第一个子串=a;

第二个子串=bba

现在检查 bba 中 a 的所有变位词对

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<length;i++){
        if(i+len<=length){
        String sub=s2.substring(i,i+len);
        char[] c2=sub.toCharArray();
        Arrays.sort(c2);
        String ss2=new String(c2);
        if(ss1.compareTo(ss2)==0)
            count++;
        }
    }
return count;
}

}

Answer 3

除了提前终止。您可以使用 HashMap，键是长度，值是相同长度的子字符串列表。存储子字符串并仅检查 'value' 内的元素。尽管您可能认为如果长度不同，它的工作方式与提前终止相同，但它有所不同并且不会出现提前终止问题。

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<x; k++){
            String str1=sc.next();
            HashMap<Integer,ArrayList<String>> sub= getSub(str1);
            int counter=0;
            for(int t=1; t<=str1.length(); t++){
                ArrayList<String> subsl= sub.get(t);
                for(int i=0; i<subsl.size()-1; i++){
                    for(int j=i+1; j<subsl.size(); j++){
                        if(isAnagram(subsl.get(j),subsl.get(i))){
                            counter++;
                        }
                    }   
                }
            }
            System.out.println(counter);
        }
    }
    public static HashMap<Integer,ArrayList<String>> getSub(String str1){
        HashMap<Integer,ArrayList<String>> ret= new HashMap<Integer,ArrayList<String>>();
        for(int i=0; i<str1.length(); i++){
            for(int j=i; j<str1.length(); j++){
                if(!ret.containsKey(str1.substring(i, j+1).length())){  
                    ArrayList<String> x= new ArrayList<String>();
                    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<a1.length(); i++){
            count1[(int)a1.charAt(i)-97]++;
            count2[(int)a2.charAt(i)-97]++;
        }
        for(int i=0; i<26; i++){
            if(count1[i]!=count2[i])
                return false;
        }
        return true;
    }
}

如果你想让它更快，然后更改 HashMap 以包含一个对象，该对象具有所有 26 个字母的计数。这显然会占用更多的内存，所以你可以有一些中间的长度，并说出字母 a、b、c（或 3 个这样的字母）的计数。为了提高检查效率，使用位操作对所有这些进行编码（长度、a 的计数、b 的计数和 c 的计数）。但请注意不要超过整数的位数。

找出子串的无序变位词对的数量

Find the number of unordered anagramic pairs of substrings

java

string

anagram

java.util.scanner