가장긴 회문

타임리밋 걸림...

import "fmt"

func Reverse(s string) (result string) {
  for _,v := range s {
    result = string(v) + result
  }
  return 
}

func GetPalindrome(l int, r int, origin string, prePalLength int) string {
    var palindrome string
    
    if r - l == 2 {
        palindrome = string(origin[l + 1])
    }
    
    // if prePalLength != 0 {
    //     start, end := l, r
    //     l -= prePalLength / 2
    //     r += prePalLength / 2
    //     if origin[l:start + 1] == Reverse(origin[end: r + 1]) {
    //         palindrome = origin[l:r + 1]
    //     }
    // }
    
    for l >= 0 && r < len(origin) {
        fmt.Println(string(origin[l]), l, string(origin[r]), r, palindrome)
        if origin[l] == origin[r] {
            palindrome = string(origin[l]) + palindrome + string(origin[r])
            l--
            r++
            continue
        } else {
            break
        }
    }
    
    return palindrome
}

func longestPalindrome(s string) string {
    i := 0
    j := 1
    curPalindrome := ""

    for j < len(s) {
        if s[i] == s[j] {
            newPalindrome := GetPalindrome(i, j, s, len(curPalindrome))
            if len(newPalindrome) > len(curPalindrome)  {
                curPalindrome = newPalindrome
            }
        }
        if j - i == 1 {
            j++
        } else if j - i == 2 {
            i++
        }
    }
    if curPalindrome == "" {
        return string(s[0])
    }
    return curPalindrome
}

O(n^2) 알고리즘

func GetPalindromeLength(l int, r int, origin string) int {
    for l >= 0 && r < len(origin) && origin[l] == origin[r] {
        l--
        r++
    }
    
    return r - l - 1 // 2n - 1
}

func longestPalindrome(s string) string {
    if s == "" || len(s) < 1 {
        return ""
    }
    
    end, start := 0, 0
    length := 0

    for i := 0; i < len(s); i++ {
        leng1, leng2 := GetPalindromeLength(i, i, s), GetPalindromeLength(i, i + 1, s)
        if leng1 < leng2 {
            length = leng2
        } else {
            length = leng1
        }
        if length > end - start {
            start = i - (length - 1) / 2 // index 0부터 시작하기 때문에 - 1
            end = i + length / 2
        }
    }
    
    return s[start: end + 1]
}