java - 使用java比较字符串的替代字符的最快方法是什么？

Question

有多个字符串从标准输入传递到该程序。第一个 int 输入 T 是传递给该程序的测试用例(字符串)的数量。具有不同替代字符的字符串是完美的。如果替代字符相同，则需要删除这两个字符中的 1 个。基本上，你必须计算，需要删除多少个字符才能获得完美的字符串？例如:ABABAB 是完美的，而 AABABAA 是不完美的。你需要删除2个A，第一个和最后一个。在AAAA中，你需要删除3个A才能得到完美的字符串。字符串输入可能非常大。计算此类删除数量的最快方法是什么？下面的代码是我写的，运行速度非常慢。

public static void main(String[] args) {
    Scanner scan = new Scanner (System.in);
    int T= scan.nextInt();
    String str;
    int count=0;
    for(int i=0; i<T; i++){
        str=scan.next();
        for(int j=0; j<str.length()-1; j++){
            if(str.charAt(j)!=str.charAt(j+1)){
                j+=2;
            }
            else{
                count++;
            }
        }
        System.out.println(count);
    }
}

Answer 1

在担心性能之前，先担心您的解决方案是否正确。对于输入 ABAAB，您的程序返回 0，但是必须删除 1 A 才能获得完美的字符串。

那么:“非常大”是什么意思？那是多少个字符？什么是“非常慢”？

您必须至少查看字符串中的每个字符一次，因此您不会获得更快的速度。但是，您也许可以进行一些优化。目前，您可能会查看单个字符两次(一次在 str.charAt(j+1) 中，一次在 str 中的下一次迭代中) .charAt(j))。当然可以以这样的方式编写算法，即字符串的每个字符都被访问恰好一次。但同样，在关注速度之前，您应该先关注正确性。