共计 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));
}
}
正文完