回文 - 是否可以使我的代码更快

Question

我有一个纯 ASCII 字符串，它要么已经是回文，要么可以通过删除一个字符来制作回文。我需要确定它是否已经是回文，如果不是，我需要找到需要删除的字符的索引。例如，如果字符串是'aaba'，则可以'aba'通过删除第一个字符将其制成回文，因此我需要返回0。我有工作代码，但我想知道是否可以使它更快，因为我需要处理许多长字符串。这是我的代码：package mainimport (    "fmt"    )func Palindrome(s string) bool {    var l int = len(s)    for i := 0; i < l / 2; i++ {        if s[i] != s[l - 1 - i] {            return false;        }    }    return true}func RemoveChar(s string, idx int) string {    return s[0:idx-1] + s[idx:len(s)]}func findIdx(s string) int {    if Palindrome(s) {        return -1    }    for i := 0; i < len(s); i++ {        if Palindrome(RemoveChar(s, i + 1)) {            return i        }    }    return -2}func main() {    var s string = "aabaab"    fmt.Println(findIdx(s))}

Answer 1

这应该比 ruakh 的解决方案更有效。你不应该使用isPalindrome（）来检查s[i + 1:len(s) - i]是回文，因为它的速度更快，以检查s[i:len(s) - i - 1]是不是回文。在下面的解决方案中，在大多数情况下， j 在函数返回之前根本不会走得太远。

func findIdx(s string) int {

    var n int = len(s) 

    for i := 0; i < n / 2; i++ {

        if s[i] != s[n - i - 1] {

             for j := 0; ;j++ {

                 if s[i + j] != s[n - 2 - i - j] {

                     return i;

                 }

                 if s[i + j + 1] != s[n - 1 - i - j] {

                     return n - 1 - i; 

                 }

             }

        }

    }

    return -1

}