首页分享 leetcode5. 最长回文子串

leetcode5. 最长回文子串

来源：花匠小妙招时间：2024-12-31 18:08

题目来源：题目

题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"

输出: "bab"

注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"

输出: "bb"

思路

思路一（暴力解法）

找到所有的字串，利用头尾指针的方式判断每个字串是否为回文串。使用头尾指针判断字串是否为回文串的时间复杂度为O(n).找每个字串的时间复杂度为O(n^2).所以总的时间复杂度为O(n^3).时间复杂度太高，通过不了本题。

思路二（中心扩展）

遍历字符串中的每个字符，判断以该字符为中间字符的回文串的最大长度。

该字符为中间字符有两种情况：

第一种是回文串的长度为奇数，该字符为最中间的一个字符，使用左右两个指针判断指向的字符是否相同，如果相同并且没有越界，则左右指针继续扩展。

第二种情况是回文串的长度为偶数，该字符为中间两个字符的左边字符，同样使用左右两个指针判断以该字符为中心的字符串是否为回文串。

思路三（动态规划）

用f(i,j)表示下标i到j的子字符串是否为回文串。f(i,j)值为true表示s[i,j]是回文串，f(i,j)的值为false，表示s[i,j]不是回文串。

回文串有这样一个特点：如果s[i,j]为回文串，则去点头尾两个字符依然为回文串，即s[i+1,j-1]依然是回文串。

当字串的长度大于2时，则有f(i,j) = f(i+1,j-1) && (Ci == Cj)

对于长度是1和2的字串，可以直接判断该字串是否为回文串。

然后建立二维布尔型数组，记录f(i，j)的值，然后找到值为true的j-i差值最大的即为要求的字串。

代码

思路二代码

public static String longestPalindrome(String s) {

int len = 0;

String subString = "";

for(int i = 0;i < s.length();i++){

int left = i - 1,right = i+1;

while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {

left--;

right++;

}

if(right - left - 1 > len){

len = right - left - 1;

subString = s.substring(left + 1,right);

}

left = i;

right = i + 1;

while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {

left--;

right++;

}

if(right - left - 1 > len){

len = right - left - 1;

subString = s.substring(left + 1,right);

}

return subString;

}

思路三代码

public static String longestPalindrome(String s) {

if(s == null || s.length() == 0)return "";

String ans = s.substring(0,1);

boolean[][] dp = new boolean[s.length()][s.length()];

for(int l = 0;l < s.length();l++){

for(int i = 0;i + l < s.length();i++){

int j = i + l;

if(l == 0){

dp[i][j] = true;

}else if(l == 1){

dp[i][j] = (s.charAt(i) == s.charAt(j));

}else {

dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i + 1][j - 1];

}

if(dp[i][j] && j - i + 1 > ans.length())ans = s.substring(i,j+1);

}

return ans;

}

总结

思路一时间复杂度为O(n^3),空间复杂度为O(1).

思路二时间复杂度为O(n^2),空间复杂度为O(n^2).

思路三时间复杂度为O(n^2),空间复杂度为O(n^2).

推荐分享

家庭养花风水知识家庭养花“五行说”

家庭养花知识大全家庭养花有什么好处

秋天养花，掌握这5点养花知识，正确管理花卉，让花健康生长

【花卉知识】养花须知：新手养花的选购技巧，不要当冤大头！