Palindrome - возможно ли сделать мой код быстрее

Question

У меня есть только ASCII-строка, которая либо уже является палиндром, либо может быть сделана палиндром, удалив один символ. Мне нужно определить, является ли это уже палиндром, а если нет, мне нужно найти индекс символа, который нужно удалить. Например, если строка 'aaba', то ее можно сделать в palindrome '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

Вот это гораздо более эффективный подход:

func findIdx(s string) int { 
    for i := 0; i < len(s)/2; i++ { 
     if s[i] != s[len(s) - i - 1] { 
      if isPalindrome(s[i+1:len(s)-i]) { 
       return i 
      } else { 
       return len(s) - i - 1 
      } 
     } 
    } 

    return -1 
} 

Он просто исходит из концов струны, пока не найдет пару байтов, должен, если строка была палиндром, но это не так. Затем он знает, что он вернет индекс одного из этих двух байтов, поэтому ему нужно только выполнить команду «это палиндром?». проверить; и не нужно использовать функцию RemoveChar, так как «это палиндром?» проверить нужно только рассмотреть среднюю часть строки (которая еще не была проверена).

Answer 2

Это должно быть немного более эффективным, чем решение руаха. Вам не нужно использовать isPalindrome(), чтобы проверить, что s[i + 1:len(s) - i] является палиндром, потому что он быстрее проверяет, что s[i:len(s) - i - 1] is не a palindrome. В приведенном ниже решении, в большинстве случаев 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 
}