题目连结
github 解题连结 解法1
github 解题连结 解法2

** 解法2的表格爆炸了，有兴趣的可以点我的github来了解**

题目意思

从s里找到最长的对称字串

解题

Longest Palindromic Substring

DP string

解题

经历整个字串==>必看其最后能够扩展多少格(符合回唯才可以再扩展)用动规去遍历整个字串

解法 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 => 建立表格babababababa表格意义 ==> 所有字串的组合 ==> 如下图babababbbababbababababbababaa/aababaababababab//bbababbabaa///aababab////bbaa/////a

我们只要判断这格是不是对称的就行了，也就是==>判断头与尾是否相同

相同: 去看减去头与尾的字串是否对称
不同: 会报这格是非对称(这样下次有相同的头尾时查找这格时就可以直接给答案

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;    }}