算法刷题-Day06_2021109

最长回文子串

知识点 字符串 穷举

描述

对于给定的由小写字母构成的字符串 s，求出其最长回文子串的长度。

子串为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。 一个字符串被称作回文串，当且仅当这个字符串从左往右读和从右往左读是相同的。

输入描述：

在一行上输入一个长度为 1≦len(s)≦350、仅由小写字母构成的字符串 s。

输出描述：

输出一个整数，表示字符串 s 的最长回文子串的长度。

示例1

输入：

cdabbacc

输出：

4

说明：

在这个样例中，"abba" 是最长的回文子串。

示例2

输入：

a

输出：

1

作答：

import java.util.Scanner;
​
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int len = s.length();
        if (len == 1) {
            System.out.println(len);
            return;
        }
        int maxLen = 1;
​
        for (int i=0; i<s.length(); i++) {
            int l1 = isHuiWen(s, i, i);
            int l2 = isHuiWen(s, i, i+1);
            maxLen = Math.max(maxLen, Math.max(l1, l2));
        }
​
        System.out.println(maxLen);
    }
​
    public static int isHuiWen(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

思路：

• 什么是回文，判断回文的思路也就是滑动窗口的思维；

• 通过遍历即穷举，将每个字符都作为可能的中心，向外拓展遍历；

• 中心需考虑奇数、偶数，奇数只有一个中心，偶数是两个中心；