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

(输入验证码)
or Ctrl+Enter