題目
#

leetcode 5 - Longest Palindromic Substring (題目說明請點連結)

題目簡述
#

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

範例
#

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" 也是一個有效答案。

Example 2:

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

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

解題思路
#

這題要求我們找出一個字串中最長的回文子串。回文是指正讀和反讀都相同的字串。我們可以使用中心擴展的方法來解決這個問題，通過從每個字符（或字符之間）開始向外擴展來找到回文。

解法
#

中心擴展

初始化 start 和 end 來記錄最長回文子串的起始和結束位置
遍歷字串中的每個字符，對於每個字符：
- 單一字元（奇數長度，例如 “aba” 的中心是 ‘b’）
- 兩個相同字元（偶數長度，例如 “abba” 的中心是 “bb”）
- 對每個中心嘗試擴展，更新最長回文子串的起始和結束位置
返回最長回文子串

步驟
#

初始化：
- 設定 start 和 end 為 0
中心擴展：
- 遍歷每個字符，計算奇數和偶數長度的回文
- 更新 start 和 end
返回結果：
- 返回 s.substring(start, end + 1)

例子說明
#

s = "babad"

i(中心)	中心類型	擴展結果	長度	更新 start/end 後結果
0(‘b’)	奇數	“b”	1	“b”
	偶數	""	0	—
1(‘a’)	奇數	“bab”	3	“bab”
	偶數	""	0	—
2(‘b’)	奇數	“aba”	3	“bab” 或 “aba”（等長可不更新）
	偶數	""	0	—
3(‘a’)	奇數	“ada”	3	不更新（等長）
	偶數	""	0	—
4(’d’)	奇數	“d”	1	—

完整程式碼
#

java

class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() < 1) return "";

        int start = 0, end = 0;

        for(int i = 0; i < s.length(); i++){
            int lenOdd = getPalindromeLen(s, i, i);
            int lenEven = getPalindromeLen(s, i, i + 1);

            int maxLen = Math.max(lenOdd, lenEven);

            if(maxLen > (end - start)){
                start = i - (maxLen - 1) / 2;
                end = i + maxLen / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    public int getPalindromeLen(String s, int left, int right){
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }

        return right - left - 1;
    }
}