Leetcode - Single Element in a Sorted Array
Leetcode - Palindrome Permutation

Leetcode - Longest Palindromic Substring

violet posted @ Mar 25, 2020 01:06:18 AM in 算法 with tags Algorithm DP Golang , 46 阅读

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

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

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

Example 2:

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

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter