performance - 回文 - 是否有可能使我的代码更快

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