一、题目描述
来源:力扣(LeetCode)
给你一个字符串 s,找到 s 中最长的回文子串。
示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd"
输出:"bb"
提示:
1 <= s.length <= 1000
s
仅由数字和英文字母组成
根据回文串的定义,正着和反着读一样,那我们是不是把原来的字符串倒置了,然后找最长的公共子串就可以了。例如 S = "caba" ,S = "abac",最长公共子串是 "aba",所以原字符串的最长回文串就是 "aba"。
关于求最长公共子串(不是公共子序列),有很多方法,这里用动态规划的方法, 整体思想就是,申请一个二维的数组初始化为 0,然后判断对应的字符是否相等,相等的话
arr [ i ][ j ] = arr [ i - 1 ][ j - 1] + 1 。
当 i = 0 或者 j = 0 的时候单独分析,字符相等的话 arr [ i ][ j ] 就赋为 1 。
arr [ i ][ j ] 保存的就是公共子串的长度。
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
String res = s.substring(0, 1);
// 枚举所有长度大于等于 2 的子串
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (j - i + 1 > maxLen && valid(s, i, j)) {
maxLen = j - i + 1;
res = s.substring(i, j + 1);
}
}
}
return res;
}
private boolean valid(String s, int left, int right) {
// 验证子串 s[left, right] 是否为回文串
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
}
暴力解法时间复杂度高,但是思路清晰、编写简单,因为编写的正确性的可能性很大,可以使用暴力匹配算法检验我们编写的其它算法是否正确。