【算法题】LeeCode 最长回文子串

共计 931 个字符，预计需要花费 3 分钟才能阅读完成。

题目

给你一个字符串 s，找到 s 中最长的回文子串。

提示:

1 <= s.length <= 1000
s 由小写英文字母组成
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。

示例1

输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

示例2

输入：s = “cbbd”
输出：”bb”

JAVA解法

import java.util.Scanner;

/**
 * 5. 最长回文子串
 *
 * @since 2022年4月25日
 */
public class LeeCode_5 {
    public static String longestPalindrome(String line) {
        int[] strs = {0, 0};
        int longest = 0;
        char[] chars = line.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            for (int j = 0; j < chars.length; j++) {
                // 找到右边的相同字符索引
                if (j < i || chars[i] != chars[j]) {
                    continue;
                }
                int l = i; // 定义最左侧指针
                int r = j; // 定义最右侧指针
                // 从两侧向中间移动，如果出现不相等，就判定不符合回文规则
                while (l <= r) {
                    if (chars[l] != chars[r]) {
                        r = -2; // 定义一个标记，表示本次区间不符合回文规则
                        break;
                    }
                    l++;
                    r--;
                }
                int tempLong;
                if (r == -2) {
                    continue;
                } else {
                    tempLong = j - i;
                }

                if (tempLong >= longest) {
                    longest = tempLong; // 最长的回文字符串长度标记一下
                    strs[0] = i; // 记录回文串左索引
                    strs[1] = j + 1; // 记录回文串右侧索引
                }
            }
        }
        return line.substring(strs[0], strs[1]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        System.out.println(longestPalindrome(line));
    }
}