5、Longest Palindromic Substring

题设(最长回文串)

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example:
Input: "cbbd"
Output: "bb"

要点

• 动态规划

1、单个字母肯定是回文串；
2、如果字符串S[i,j]，S[i] != S[j]，肯定不是回文串；
3、如果字符串S[i,j]，S[i] == S[j]，那么如果S[i+1,j-1]是回文串，则S[i,j]是回文串。
因此，可以用DP[i][j]记录S[i,j]是否为回文串，然后按照子串的长度进行循环，动态更新DP的同时，不断更新记录的最长子串长度以及对应的子串，最后输出需要的值即可。

    public static String longestPalindrome(String s){
        int len = s.length();
        if(len == 0)
            return "";
        else if (len == 1) {
            return s;
        }
        else {
            // 初始化动态规划数组
            int[][] isPalindrom = new int[len][len];
            for(int i = 0;i < len;i++){
                for(int j = 0;j < len;j++){
                    if(i >= j)
                        isPalindrom[i][j] = 1;
                    else
                        isPalindrom[i][j] = 0;
                }
            }
    
            int maxSubstringLen = 0; // 记录最长长度
            int left = 0; // 记录最后结果
            int right = 0; // 记录最后结果
            for(int substringLen = 1;substringLen < len;substringLen++){ // substringLen代表子串长度
                for(int leftPosi = 0;leftPosi < len - substringLen;leftPosi++){ // leftPosi代表子串左端位置
                    int rightPosi = leftPosi + substringLen; // 子串右边位置;
                    if(s.charAt(leftPosi) != s.charAt(rightPosi)){ // 首尾不等肯定不是回文串
                        isPalindrom[leftPosi][rightPosi] = 0;
                        continue;
                    }else{
                        isPalindrom[leftPosi][rightPosi] = isPalindrom[leftPosi + 1][rightPosi - 1]; // 动归
                        if(isPalindrom[leftPosi][rightPosi] == 1){ // 是回文串
                            if(maxSubstringLen < substringLen + 1){
                                maxSubstringLen = substringLen + 1;
                                left = leftPosi;
                                right = rightPosi;
                            }
                        }
                        
                    }
                }
            }
            
            return s.substring(left , right + 1);
            
        }