5. 最长回文子串

题目

给出一个字符串，求它的子串中是回文串且最长的那一个。
如abba 输出abba
abccbe 输出bccb

思路

这一题适合采用动态规划来做。

定义状态：

dp[i][j]：从下标i到j（包括j）的子串（i<=j），是否为回文串(true or false)

状态转移：

dp[i][j] = (dp[i+1][j-1] == true && arr[i] == arr[j])

初始化：

• dp[i][i] = true （0<=i<=n-1）长度为1的子串都是回文串
• dp[i][i-1] = true(1<=i<=n-1)
  其中第二条在判断长度为2的子串时有用。

代码思路：

根据子串的长度遍历，从2开始到最大的arr.length结束。因为长度len的子串要根据长度为len-1的子串是否为回文串来判断。

AC了的代码

import java.util.Scanner;

class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            String s = scanner.nextLine();
            System.out.println(solution.longestPalindrome(s));
        }
    }

    public String longestPalindrome(String s) {
        int len = s.length();
        if(len <= 1) return s;

        String str = s;
        char[] arr = str.toCharArray();

        boolean[][] dp = new boolean[len][len];
        dp[0][0] = true;
        for(int i = 1; i < len; i++) {
            dp[i][i] = true;
            dp[i][i-1] = true;
        }
        int r = 0,l = 0;

        for(int k = 2; k <= len; k++) {
            for(int i = 0; i <= len - k; i++) {
                int j = i + k - 1;
                if(dp[i+1][j - 1] && arr[i] == arr[j]) {
                    dp[i][j] = true;
                    // System.out.println("l = " + i + "\tr = " + j);
                    // if((j - i) > (r - l)) {
                        l = i; r = j;
                    // }
                        // break;
                }
            }
        }

        // for(int i = 0; i < len - 1; i++) {
        //  for(int j = i + 1; j < len; j++) {
        //      if(dp[i+1][j - 1] && arr[i] == arr[j]) {
        //          dp[i][j] = true;
        //          System.out.println("l = " + i + "\tr = " + j);
        //          if((j - i) > (r - l)) {
        //              l = i; r = j;
        //          }
        //      }
        //  }
        // }

        return s.substring(l,r+1);
    }
}