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

Question

问题：

给定 ascii[az] 范围内的小写字母字符串，确定要删除的字符索引，以将该字符串更改为回文。如果字符串无法转换为回文或已经是回文，则返回 -1，否则返回要删除的字符的索引。

我的解决方案：

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，以下一个或所有测试用例均失败（无法确定是哪一个）：

1. quyjjdcgsvvsgcdjjyq
2. hgygsvlfwcwnswtuhmyaljkqlqjjqlqkjlaymhutwsnwcflvsgygh
3. fgnfnidynhxebxxxfmxixhsruldhsaobhlcggchboashdlurshxixmfxxxbexhnydinfngf
4. bsyhvwfuesumsehmytqioswvpcbxyolapfywdxeacyuruybhbwxjmrrmjxwbhbyuruycaexdwyfpaloyxbcpwsoiqtymhesmuseufwvhysb
5. fvyqxqxynewuebtcuqdwyetyqqisappmunmnldmkttkmdlnmnumppasiqyteywdquctbeuwenyxqxqyvf
6. mmbiefhflbeckaecprwfgmqlydfroxrblulpasumubqhhbvlqpixvvxipqlvbhqbumusaplulbrxorfdylqmgfwrpceakceblfhfeibmm
7. tpqknkmbgasitnwqrqasvolmevkasccsakvemlosaqrqwntisagbmknkqpt
8. 左旋右旋
9. pcoitfiptvcxrvoalqmfpnqyhrubxspplrftomfehbbhefmotfrlppsxburhyqnpfmqlaorxcvtpiftiocrp
10. kjowoemiduaaxasnqghxbxkiccikxbxhgqnsaxaaudimeowojk

我的输出：

1. 1
2. 8
3. 33
4. 23
5. 24
6. 43
7. 20
8. -1
9. 14
10. -1

我在本地调试了代码，根据我的理解，这个测试用例运行良好。请帮助我理解代码有什么问题。

注意：我可以用其他替代方法（更简单的方法）来做到这一点，解决方案可以在网上找到，但我试图了解我的java代码有什么问题。谢谢。

Answer 1

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

通过首先检查原始字符串是否是回文，您可以找到它失败的位置，这样您就只剩下两种删除的可能性。所以你只需要尝试这两个。此外，您实际上不必执行删除操作。您可以跳过相关字符并通过跳过相应索引继续回文检查。

这是一个可能的实现：

    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;        
    }