題目連結
github 解題連結 解法1
github 解題連結 解法2

** 解法2的表格爆炸了，有興趣的可以點我的github來了解**

題目意思

從s裡找到最長的對稱字串

解題

Longest Palindromic Substring

DP string

解題

1. 經歷整個字串==>必看其最後能夠擴展多少格(符合回唯才可以再擴展)
2. 用動規去遍歷整個字串

解法 1

• 直接擴展去找

code

class Solution {
public:
    pair<int, int> expandAroundCenter(string s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            left--;
            right++;
        }
        return {left + 1, right - 1};
    }

    string longestPalindrome(string s) {
        int start = 0, end = 0;
        
        for (int i = 0; i < s.size(); i++) {
            auto [left1, right1] = expandAroundCenter(s, i, i);
            auto [left2, right2] = expandAroundCenter(s, i, i + 1);
            if (right1 - left1 > end - start) {
                start = left1;
                end = right1;
            }
            if (right2 - left2 > end - start) {
                start = left2;
                end = right2;
            }
        }
        return s.substr(start, end - start + 1);
    }
};

解法 2

根據題意，而且標籤有dp，基本可以先建表

• 假設題目是bababa => 建立表格

• 表格意義 ==> 所有字串的組合 ==> 如下圖

• 我們只要判斷這格是不是對稱的就行了，也就是==>判斷頭與尾是否相同

  相同: 去看減去頭與尾的字串是否對稱
  不同: 會報這格是非對稱(這樣下次有相同的頭尾時查找這格時就可以直接給答案

  

class Solution {
    public String longestPalindrome(String s) {
        String ans = "";
        int n = s.length();
        ans+=s.charAt(0);

        boolean[][] dp = new boolean[n][n];

        for(int i = 0;i < n;i++) dp[i][i] = true;

        //size is 2
        for(int i = 0;i < n;i++){
            if(i + 1 < n && s.charAt(i) == (s.charAt(i+1))){
                dp[i][i+1] = true;
                if(ans.length() < 2) ans = s.substring(i,i+2);
            }
        }

        // size > 2
        // len + start < n
        for(int len = 2;len<n;len++){
            for(int start = 0;len + start < n;start++){
                int end = start + len;
                if(s.charAt(start) == (s.charAt(end)) && dp[start+1][end-1]){
                    dp[start][end] = true;
                    
                    String temp = s.substring(start,end+1);

                    ans = temp.length() > ans.length() ? (temp): (ans); 
                }
            }
        }


        return ans;
    }
}