Hackerrank - 解决回文索引解决方案

Question

问题：

给定一串 ascii[a-z] 范围内的小写字母，确定要删除的字符的索引，以将字符串更改为回文。如果字符串不能转换为回文或者已经是回文只是 return -1 else return 要删除的字符的索引。

我的解决方案：

public static int palindromeIndex(String s) {

    if(p(s)){
        return -1;
    }

    StringBuilder sb = new StringBuilder(s);

    for(int i=0; i<s.length(); i++){

        sb.deleteCharAt(i);
        if(p(sb.toString())){
            return i;
        }
        sb.insert(i,s.charAt(i));
    }


    return -1;

}

private static boolean p(String s){

    for(int i=0; i<s.length()/2; i++){
        if(s.charAt(i) != s.charAt(s.length() - i - 1)){
            return false;
        }
    }

    return true;
}

根据 hackerrank，以下一个或所有测试用例（无法确定是哪个）失败：

quyjjdcgsvvsgcdjjyq
hgygsvlfwcwnswtuhmyaljkqlqjjqlqkjlaymhutwsnwcflvsgygh
fgnfnidynhxebxxxfmxixhsruldhsaobhlcggchboashdlurshxixmfxxxbexhnydinfngf
bsyhvwfuesumsehmytqioswvpcbxyolapfywdxeacyuruybhbwxjmrrmjxwbhbyuruycaexdwyfpaloyxbcpwsoiqtymhesmuseufwvhysb
fvyqxqxynewuebtcuqdwyetyqqisappmunmnldmkttkmdlnmnumppasiqyteywdquctbeuwenyxqxqyvf
mmbiefhflbeckaecprwfgmqlydfroxrblulpasumubqhhbvlqpixvvxipqlvbhqbumusaplulbrxorfdylqmgfwrpceakceblfhfeibmm
tpqknkmbgasitnwqrqasvolmevkasccsakvemlosaqrqwntisagbmknkqpt
lhrxvssvxrhl
prcoitfiptvcxrvoalqmfpnqyhrubxspplrftomfehbbhefmotfrlppsxburhyqnpfmqlaorxcvtpiftiocrp
kjowoemiduaaxasnqghxbxkiccikxbxhgqnsaxaaudimeowojk

我的输出：

1
8
33
23
24
43
20
-1
14
-1

我在本地调试代码，据我了解，这个测试用例运行良好。请帮我轻描淡写，代码有什么问题。

注意：我可以用其他替代方法（更简单的方法）来解决，在线提供解决方案，但我试图理解，我的作品有什么问题java 代码。谢谢

Answer 1

您的代码在某些测试用例上超时。尝试删除每个字符然后检查它是否是回文不是很有效。

首先检查原始字符串是否是回文，你可以找到它失败的地方，这给你留下了 2 种删除的可能性。所以你只需要尝试这两个。此外，您实际上不必执行删除。您可以直接跳过关注的字符，跳过相应的索引继续回文检查。

这是一个可能的实现：

    public static int palindromeIndex(String s) {
        int start = 0;
        int end = s.length() - 1;
        while (start < end && s.charAt(start) == s.charAt(end)) {
            start++;
            end--;
        }
        if (start >= end) return -1; // already a palindrome
        // We need to delete here
        if (isPalindrome(s, start + 1, end)) return start;
        if (isPalindrome(s, start, end - 1)) return end;
        return -1;
    }

    public static boolean isPalindrome(String s, int start, int end) {
        while (start < end && s.charAt(start) == s.charAt(end)) {
            start++;
            end--;
        }
        return start >= end;        
    }

Hackerrank - 解决回文索引解决方案

Hackerrank - Solving Palindrom Index Solution

java

algorithm

logic

reverse

palindrome