java - 查找大子串的字谜计数时出错

Question

我正在尝试为输入字符串的每个子字符串检查和计算字谜对。

例如，如果输入字符串是 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();
    }
}

Answer 1

这是您的问题的一部分:

    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 似乎没有声明。我懒得尝试解决这个问题。

链接:

• https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_ ⋯
• https://www.wolframalpha.com/input/?i=n(n%2B1)%2F2
• https://en.wikipedia.org/wiki/Big_O_notation