Leetcode - Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: "cbbd"
Output: "bb"

func longestPalindrome(s string) string {
    if len(s) == 0 || len(s) == 1{
        return s
    }
    size := len(s)
    dp := make([][]bool, size)
    for i := 0; i < len(dp); i++ {
        dp[i] = make([]bool, size)
    }
    
    for i := 0; i < size; i++ {
        dp[i][i] = true
    }
    
    for i := 1; i < size; i++ {
        if s[i] == s[i-1] {
            dp[i-1][i] = true
        }
    }
    
    for length := 3; length <= size; length++ {
        for i := 0; i < size-length+1; i++ {
            j := i + length - 1
            if s[i] == s[j] && dp[i+1][j-1] {
                dp[i][j] = true
            }
        }
    }
    
    max := 0
    maxi := 0
    maxj := 0
    for i := 0; i < size; i++ {
        for j := 0; j < size; j++ {
            if dp[i][j] && j - i > max {
                max = j - i
                maxi = i
                maxj = j
            }
        }
    }
    
    return s[maxi:maxj+1]
}

• 相关文章
• 全局相关文章