Palindrome - 내 코드를 더 빠르게 만들 수 있습니까?

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

훨씬 더 효율적인 방법입니다 : 여기

내 코드는 바이트 쌍을 찾을 때까지 그냥 문자열의 끝에서 진행

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

이것은 ruakh 솔루션보다 약간 더 효율적입니다. s[i + 1:len(s) - i]이 회문인지 확인하려면 isPalindrome()을 사용할 필요가 없습니다. 왜냐하면 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 
}