题目：给你一个字符串 s，找到 s 中最长的回文子串。

输入：s = "babad"
输出："bab"

原题链接：https://leetcode-cn.com/problems/longest-palindromic-substring/

 

思路：

1. 动态规划

class Solution {
        public String longestPalindrome(String s) {
            int max = 1, n = s.length(), start = 0, cur = 0;
            String result = s.substring(0, 1);
            int dp[][] = new int[n + 1][n + 1];
            char c[] = s.toCharArray();
            for(int i=n-1;i>=0;i--)
            {
                for(int j=i+1;j<n;j++)
                {
                    if(j-i<=2)
                    {
                        if(c[i]==c[j]) { dp[i][j]=1; cur=j-i+1;}
                    }else if(c[i]==c[j]&&dp[i+1][j-1]==1){ dp[i][j]=1; cur=j-i+1;}
                    if(dp[i][j]==1&&cur>max) {max=cur;start=i;}
                }
            }
            return s.substring(start, start + max);
        }
    }

 

2. 基于中心线枚举

以每个点为中心，双向指针判断最大回文子串

class Solution {
        public String longestPalindrome(String s) {
            int max = 1, n = s.length(), start = 0, cur = 0;
            String result = s.substring(0, 1);
            int dp[][] = new int[n + 1][n + 1];
            char c[] = s.toCharArray();
            for(int i=n-1;i>=0;i--)
            {
                for(int j=i+1;j<n;j++)
                {
                    if(j-i<=2)
                    {
                        if(c[i]==c[j]) { dp[i][j]=1; cur=j-i+1;}
                    }else if(c[i]==c[j]&&dp[i+1][j-1]==1){ dp[i][j]=1; cur=j-i+1;}
                    if(dp[i][j]==1&&cur>max) {max=cur;start=i;}
                }
            }
            return s.substring(start, start + max);
        }
    }