一、相关题目

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

二、解题思路

1、朴素暴力法（不可取）

扫描所有的字串，记录最长的，复杂度为11+22+33+…+nn，即O(n)。

2、动态规划

P(i, j) 代表从i到j的字串是否为回文串
P(i, i)=true, P(i, i + 1)=(S== S)
P(i, j) = P(i + 1, j - 1) && (S== S)

3、最长相似串

三、总结

附录

动态规划代码

public String longestPalindrome(String s) {
        if(s == null || s.isEmpty()) {
            return "";
        }
        int len = s.length();
        String result = s.substring(0, 1);
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        for (int i = 0; i < len - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                result = s.substring(i, i + 2);
            }
        }
        // loop for length
        for (int l = 3; l <= len; l++) {
            int lastIdx = len - l;
            for (int i = 0; i <= lastIdx; i++) {
                int j = i + l - 1;
                if (dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = true;
                    if (l > result.length()) {
                        result = s.substring(i, j + 1);
                    }
                }
            }
        }
        return result;
    }