跳轉至

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, 如果頭尾相同, 則去掉頭尾後可看是合是回文. 如果頭尾不同則不是回文

來源

解答

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 <= len(s); length++ {
        for start := 0; start < len(s)-length+1; start++ {
            end := start + length - 1
            if s[start] != s[end] {
                // 字頭字尾不同, 不是回文
                continue
            } else if length < 3 {
                // 長度為2且字頭字尾相同, 則為回文
                dp[start][end] = true
            } else {
                // 狀態轉移 : 去掉字頭字尾, 判斷是否還是回文
                dp[start][end] = dp[start+1][end-1]
            }
            if dp[start][end] && (end-start+1) > len(result) {
                result = s[start : end+1]
            }
        }
    }
    return result
}