一、题目描述
给你一个字符串 s,找到 s 中最长的回文子串。
示例 1:
输入:s = “babad”
输出:“bab”
解释:“aba” 同样是符合题意的答案。
示例 2:
输入:s = “cbbd”
输出:“bb”
示例 3:
输入:s = “a”
输出:“a”
示例 4:
输入:s = “ac”
输出:“a”
提示:
1 <= s.length <= 1000
s 仅由数字和英文字母(大写和/或小写)组成
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、完整代码
public class Solution {
public static void main(String[] args) {
String test_data = "ba1221";
System.out.println(longestPalindrome(test_data));
}
public static String longestPalindrome(String s) {
//保存回文子串
String sub_longest_str = "";
int s_length = s.length();
if (s_length < 1 || s_length > 1000) {
return sub_longest_str;
}
if (s_length == 1) {
return s;
}
for (int i = 0; i < s_length; i++) {
String s1 = find_palindrome(s, i, i);
String s2 = find_palindrome(s, i, i + 1);
sub_longest_str = sub_longest_str.length() > s1.length() ? sub_longest_str : s1;
sub_longest_str = sub_longest_str.length() > s2.length() ? sub_longest_str : s2;
}
return sub_longest_str;
}
private static String find_palindrome(String s, int i, int j) {
while (i >= 0 && j < s.length()) {
if (s.charAt(i) != s.charAt(j)) {
break;
} else {
i--;
j++;
}
}
return s.substring(i + 1, j);
}
}