执行特殊回文字符串程序失败的测试用例

Question

• 我试图解决黑客排名问题，以计算字符串中包含的特殊回文字符串的数量。
• 对于特殊回文字符串，所有字符都应该相同，除中间字符外，所有字符都是相同的
• 例如，string = asasd，那么回文字符串是{a，s，a，s，d，asa，sas}
• 在这个程序中，两个测试用例分别用字符串asasd和aaaa传递。
• 一个测试用例失败的字符串for阿里巴巴
• 我研究检查第二种情况，但我对执行死刑感到震惊。
• 你们能帮我解决你们的建议吗？
• 提供以下全部代码：

import java.util.Scanner;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class MyClass {
    public static void main(String args[]) {
        int counter=0;
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // read an integer from input stream.
        String s = scanner.next();
        char string_array[] = s.toCharArray();
        for(int i=0; i<s.length(); i++){
            for(int j=i; j<=s.length(); j++){
                if(i != j){
                    String s1 = s.substring(i,j);
                    String rev = "";
                    for(int z=0; z<s1.length(); z++){
                    rev = rev + s1.charAt(s1.length()-1-z);
                    }
                    //System.out.println("s1=" + s1 +  "rev=" + rev);
                    int count = s1.compareTo(rev);
                    if(count == 0){
                    counter++;
                }
                }
            }

        }
        System.out.println(counter);
}

Answer 1

您的算法没有检查字符相等的特殊回文要求。以下算法添加了这样的检查：

public class MyClass {
    public static void main(String args[]) {
        int counter=0;
        String s = "abcbaba";
        char string_array[] = s.toCharArray();
        for(int i=0; i<s.length(); i++){
            for(int j=i; j<=s.length(); j++){
                if(i != j){
                    String s1 = s.substring(i,j);
                    String rev = "";
                    char complianceChar = s1.charAt(0);
                    boolean isSpecialPalindrom = true;
                    boolean isLengthEven = s1.length()%2==0;
                    for(int z=0; z<s1.length(); z++) {
                        char c = s1.charAt(s1.length()-1-z);
                        rev = rev + c;
                        boolean isMiddleChar = (z == (s1.length()-1)/2);
                        if(isSpecialPalindrom && (isLengthEven || !isMiddleChar)) {
                            isSpecialPalindrom = (c == complianceChar);
                        }
                    }
                    int count = s1.compareTo(rev);
                    if(count == 0 && isSpecialPalindrom){
                        System.out.println(rev);
                        counter++;
                    }
                }
            }
        }
        System.out.println(counter);
    }
}

产出如下：

a
b
bcb
c
b
bab
a
aba
b
a
10