题解 | #最长回文子串#

题解

此题可以使用中心扩散法进行解答。

解题思路：

遍历整个字符串，每个字符都有两种可能：1.以当前下标为中心进行查找回文长度。2.以当前下标和下个值之间的空格为中心进行扩散。

例如：下边 i = 2时，会右如下的两种情况。

1.以 i 为中心扩散。

2.以i，i+1中的空格为中心。

代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.next();
            int count = 1; // 最大回文长度，一个字符也表示回文，长度为1
            for (int i = 0; i < str.length(); i++) {
                // 情况一：以i为中心，进行两边扩散
                count = Math.max(count, cal(str, count, i - 1, i + 1));
                // 情况二：以i,i+1中间空格为中心，进行两边扩散
                count = Math.max(count, cal(str, count, i, i + 1));
            }
            System.out.println(count);
        }
    }

    // 计算当前下标下左右回文长度
    public static int cal(String str, int count, int left, int right) {
        while (left >= 0 && right < str.length() &&
                str.charAt(left) == str.charAt(right)) {
            int len = right - left + 1;
            if (len > count) {
                count = len;
            }
            left--;
            right++;
        }
        return count;
    }
}