我正在尝试为输入字符串的每个子字符串检查和计算字谜对。
例如，如果输入字符串是 mom，则变位词对是 m,m 和 mo,om。
该代码运行良好，并通过了三个字符串测试用例。但是由于长输入字符串的超时限制，代码被终止，例如:
ifailuhkqqhucpoltgtyovarjsnrbfpvmupwjjjfiwwhrlkpekxxnebfrwibylcvkfealgonjkzwlyfhhkefuvgndgdnbelgruel
我尝试并研究了这个问题，但我对这个错误感到震惊。 C你们能用您的建议帮助我解决问题吗？
提供以下代码:
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
// Complete the sherlockAndAnagrams function below.
static int sherlockAndAnagrams(String s) {
for(int i=0; i<s.length(); i++){
for(int j=i+1; j<=s.length(); j++){
sArray[index] = s.substring(i,j);
index++;
//System.out.println(s.substring(i,j));
//System.out.println(Arrays.toString(sArray));
}
}
for(int i=0; i<sArray.length; i++){
for(int j=i; j< sArray.length; j++){
if(i != j){
if(null == sArray[i])
break;
if(null == sArray[j])
break;
char[] sArray1 = sArray[i].toCharArray();
char[] sArray2 = sArray[j].toCharArray();
//System.out.println(sArray1);
//System.out.println(sArray2);
//int index_str = 0;
Hashtable<Character, Integer>sHash1 = new Hashtable<Character, Integer>();
Hashtable<Character, Integer>sHash2 = new Hashtable<Character, Integer>();
for (int k = 0; k < sArray1.length; k++) {
if (sHash1.get(sArray1[k]) == null) {
sHash1.put(sArray1[k], 1);
}
else {
Integer c = (int)sHash1.get(sArray1[k]);
sHash1.put(sArray1[k], ++c);
}
}
// Mapping second String
for (int l = 0; l < sArray2.length; l++) {
if (sHash2.get(sArray2[l]) == null)
sHash2.put(sArray2[l], 1);
else {
Integer d = (int)sHash2.get(sArray2[l]);
sHash2.put(sArray2[l], ++d);
}
}
if(sHash1.equals(sHash2)){
count++;
}
}
}
}
}*/
//System.out.println(sHash);
return count;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int q = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int qItr = 0; qItr < q; qItr++) {
String s = scanner.nextLine();
int result = sherlockAndAnagrams(s);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
}
bufferedWriter.close();
scanner.close();
}
}
最佳答案
这是您的问题的一部分:
for(int i=0; i<s.length(); i++){
for(int j=i+1; j<=s.length(); j++){
sArray[index] = s.substring(i,j);
index++;
}
}
substring 方法返回一个新的字符串对象。您正在为每个可能的子字符串分配内存。
您创建的新字符串对象的数量可以用以下公式粗略计算:n*(n+1)/2。那东西长得非常快。例如，对于 n = 10，它是 55，对于 n = 50，它已经是 1275。
因此对于长字符串，您的代码可能已经因为此处内存不足而崩溃。
这是你问题的第二部分:
for(int i=0; i<sArray.length; i++){
for(int j=i; j< sArray.length; j++){
您将每个子字符串与每个子字符串进行比较。迭代次数可以再次用 n*(n+1)/2 计算。当你有一个长度为 50 的字符串时，它有超过 1000 个子字符串，即超过 500000 次迭代。
此外:在每次迭代中，您都会创建两个字符数组和两个哈希表。至少它们在每次循环后都会被丢弃，因此内存应该不是问题。但速度可能。
我认为这就是长字符串超时的原因。
这里有一组不完整的关于如何解决这个问题的提示:
- 在第一个大循环中，只需保存索引(i 和 j)以供进一步使用，而不是为每个子字符串分配一个完整的新字符串。
- 在第二个大循环中，您重复计算子字符串。例如，您将子字符串 0 与 1、2、3... 进行比较，然后您将子字符串 1 与 2、3... 进行比较，因此子字符串 2 已被计算两次。最后一个子串将对其之前的每个子串重复计算。您可以尝试保存结果以防止重新计算。但这会再次消耗内存。它始终是内存和计算周期的权衡。
- 也许你可以不用 char 数组。您可以像遍历数组一样遍历字符串。
- 也许你可以不用哈希表。直接比较字符就可以了。
我无法编译您的代码，因此无法验证我的假设。 } 太多，sArray 似乎没有声明。我懒得尝试解决这个问题。
链接:
关于java - 查找大子串的字谜计数时出错，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56471623/