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

Question

我有一个纯 ASCII 字符串，它要么已经是回文，要么可以通过删除一个字符来制作回文。我需要确定它是否已经是回文，如果不是，我需要找到需要删除的字符的索引。例如，如果字符串是'aaba'，则可以'aba'通过删除第一个字符将其制成回文，因此我需要返回0。

我有工作代码，但我想知道是否可以使它更快，因为我需要处理许多长字符串。

这是我的代码：

package main

import (

    "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 {&nbsp; &nbsp; var n int = len(s)&nbsp;&nbsp; &nbsp; for i := 0; i < n / 2; i++ {&nbsp; &nbsp; &nbsp; &nbsp; if s[i] != s[n - i - 1] {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for j := 0; ;j++ {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if s[i + j] != s[n - 2 - i - j] {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return i;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if s[i + j + 1] != s[n - 1 - i - j] {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return n - 1 - i;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return -1}