最长回文子串

回文串是一个正读和反读都一样的字符串，比如level或者noon等等就是回文串。

5.最长回文子串

题目：

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

示例1：

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

示例2：

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

解题思想：

• 主要分两种情况：奇数或者是偶数来判断。比如在第二个位置a处：

• 1、首先假设以奇数开始，以a为中心点，向两边扩展移动，并判断两端的字符是否一样，在记录这个回文串的长度；

  image.png

• 2、然后在假设以偶数开始，以ab为中心点，向两边扩展移动，并判断两端的字符是否一样，在记录这个回文串的长度；

image.png

• 3、依次这样遍历即可得到最长的回文子串。

package com.zhoujian.solutions.leetcode;

import java.util.Scanner;

/**
 * @author zhoujian123@hotmail.com 2018/3/27 16:39
 */
public class A005 {

    private static int lo, maxLen;

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

        for (int i = 0; i < len-1; i++) {
            //假设是奇数
            extendPalindrome(s, i, i);  //assume odd length, try to extend Palindrome as possible
            //假设是偶数
            extendPalindrome(s, i, i+1); //assume even length.
        }
        return s.substring(lo, lo + maxLen);
    }

    private static void extendPalindrome(String s, int j, int k) {
        while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
            j--;
            k++;
        }
        if (maxLen < k - j - 1) {
            //记录回文串的首尾的地址
            lo = j + 1;
            maxLen = k - j - 1;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
//        String s = "babacd";
        String palindrome = longestPalindrome(line);
        System.out.println(palindrome);
    }
}

结果如下：

image.png

时间复杂度为O(n^2)