背景描述

原题地址：

https://leetcode-cn.com/problems/longest-palindromic-substring/

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

思路分析

1. 暴力解法

2. 基于暴力解法想到的动态规划解法

3. 中心扩展法

代码实现

动态规划解法

public class MyDpSolution {

    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) {
            return "";
        }
        boolean[][] dp = new boolean[s.length()][s.length()];
        for(int i = 0; i < s.length(); i++) {
            // i表示规格
            for(int j = 0; j < s.length() - i; j++){
                if(i == 0){
                    dp[i][j] = true;
                } else if(i == 1) {
                    dp[i][j]= s.charAt(j) == s.charAt(j+1);
                } else {
                    dp[i][j] = s.charAt(j) == s.charAt(j+i) && dp[i-2][j+1];
                }
            }
        }
        for(int i = s.length() - 1; i >= 0; i--) {
            for(int j = 0; j + i < s.length(); j++) {
                if(dp[i][j]) {
                    return s.substring(j, j + i + 1);
                }
            }
        }
        return "";
    }

}

中心扩展法

public class MyCenterExternSolution {

    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) {
            return "";
        }
        if(s.length() == 1) {
            return s;
        }
        int max_m = 0;
        int max_n = 0;
        int max = 0;
        for(int i = 1; i < s.length() * 2; i++) {
            int m,n,len=0;
            if((i & 1) == 0) {
                // i是偶数，说明中心点在一个字母上
                m = i / 2;
                n = i / 2;
            } else {
                // i是奇数，说明中心点在字母之间
                m = (i - 1) / 2;
                n = (i + 1) / 2;
            }
            while(m >= 0 && n < s.length() && s.charAt(m) == s.charAt(n)) {
                m--;
                n++;
                len = n - m;
            }
            if(len > max) {
                max = len;
                max_m = m+1;
                max_n = n-1;
            }
        }
        return s.substring(max_m, max_n + 1);
    }

}