0005.Longest Palindromic Substring

題目

Given a string s, return the longest palindromic substring in s.

A string is called a palindrome string if the reverse of that string is the same as the original string.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

題目大意

給你一個字符串 s，找到 s 中最長的回文子串。

解題思路

• 每一個字符本身都是回文
• 長度為 2, 且首尾字符相同則為回文
• 長度>=3, 如果頭尾相同, 則去掉頭尾後可看是合是回文. 如果頭尾不同則不是回文

來源

• https://leetcode.com/problems/longest-palindromic-substring/
• https://leetcode.cn/problems/longest-palindromic-substring/solutions/1348874/s-by-xext-5zk3/

解答

package longestpalindromicsubstring

func longestPalindrome(s string) string {
    dp := make([][]bool, len(s))
    result := s[0:1]

    for i := 0; i < len(s); i++ {
        dp[i] = make([]bool, len(s))
        dp[i][i] = true // 每個字符本身都是回文
    }
    for length := 2; length <= 1="" 3="" len(s);="" length++="" {="" for="" start="" :="0;" <="" len(s)-length+1;="" start++="" end="" +="" length="" -="" if="" s[start]="" !="s[end]" 字頭字尾不同,="" 不是回文="" continue="" }="" else="" 長度為2且字頭字尾相同,="" 則為回文="" dp[start][end]="true" 狀態轉移="" 去掉字頭字尾,="" 判斷是否還是回文="" &&="" (end-start+1)=""> len(result) {
                result = s[start : end+1]
            }
        }
    }
    return result
}