我要招人

去企业版

首页 > 试题广场 >

最长回文子串

[编程题]最长回文子串

热度指数：560 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

示例1

输入

"cbbd"

输出

"bb"

算法知识视频讲解

皮卡皮卡01001！

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String longestPalindrome (String s) {
        // write code here
        String ans = "";
        int max = 0;
        int len = s.length();
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j <= len; j++) {
                //得到所有的字串
                String tmp = s.substring(i, j);
                if (isPalindromic(tmp) && tmp.length() > max) {
                    ans = tmp;
                    max = j - i;
                }
            }
        }
        return ans;
    }
    //判断是否是回文子串
    private static boolean isPalindromic(String s) {
        int len = s.length();
        for (int i = 0; i < len / 2; i++) {
            if (s.charAt(i) != s.charAt(len - i - 1)) {
                return false;
            }
        }
        return true;
    }
}

发表于 2021-10-11 16:49:42 回复(1)

王治珺

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param s string字符串
* @return string字符串
*/
public String longestPalindrome (String s) {
// write code here
boolean[][] dp = new boolean[s.length()][s.length()];
int left = 0, right = 0, len = 0;

for (int i = 0; i < s.length(); ++i) {
for (int j = 0; j < i; ++j) {
dp[j][i] = (s.charAt(i) == s.charAt(j) && (i - j < 2 || dp[j + 1][i - 1]));
if (dp[j][i] && len < i - j + 1) {
len = i - j + 1;
left = j;
right = i;
}
}
dp[i][i] = true;
}
return s.substring(left, right + 1);
}
}

发表于 2021-02-21 11:21:03 回复(0)

C/C++

在攒经验的外卷侠很活泼

char* Palindrome(char *s, int l, int r)

{

while (l >= 0 && r < strlen(s) && s[l] == s[r]) {

l--;

r++;

}

// 返回以 s[l] 和 s[r] 为中心的最长回文串

char *result = (char *)malloc(r - l);

strncpy(result, s + l + 1, r - l - 1);

result[r - l - 1] = '\0';

return result;

}

char* longestPalindrome(char *s)

{

char res[100000] = {0};

int i;

int len = strlen(s);

for (i = 0; i < len; i++) {

char *s1 = Palindrome(s, i, i);

char *s2 = Palindrome(s, i, i + 1);

if (strlen(res) < strlen(s1)) {

strcpy(res, s1);

}

if (strlen(res) < strlen(s2)) {

strcpy(res, s2);

}

free(s1);

free(s2);

}

char *result = (char *)malloc(strlen(res) + 1);

strcpy(result, res);

return result;

}

发表于 2023-11-02 10:09:29 回复(0)

kahvehxkebejakakka

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string func(string& s,int left,int right){
        while(left>=0&&right<s.size()&&s[left]==s[right]){
            left--;
            right++;
        }
        string ret=s.substr(left+1,right-1);
        return ret;
    }
    string longestPalindrome(string s) {
        // write code here
        string ret;
        string s1,s2;
        for(int i=1;i<s.size()-1;i++){
            s1=func(s,i,i);
            s2=func(s,i,i+1);
            int l1=s1.size();
            int l2=s2.size();
            if(l1>l2&&l1>ret.size()){
                ret.clear();
                ret=s1;
            }else if(l2>l1&&l2>ret.size()){
                ret.clear();
                ret=s2;
            }
        }
        return ret;
    }
};

发表于 2022-08-17 20:48:07 回复(0)

Python

牛客440548025号

class Solution:
def longestPalindrome(self , s ):
# write code here
res = {}
for i in range(len(s)):
for j in range(i+1, len(s)+1):
if s[i:j] == s[i:j][::-1]:
res[j-i] = s[i:j]
if res != "":
return res[max(res)]

发表于 2022-07-31 10:22:01 回复(0)

瑞士军刀

class Solution:
def longestPalindrome(self , s ):
m = 0
t = 0
for i in range(len(s)):
if i-m-1 >= 0 and s[i-m-1:i+1] == s[i-m-1:i+1][::-1]:#参数m设定机制：如果后续子串长度不超过m时，判断将不通过，这会导致一个后果：有多个子串等长时代码不适用，只会输出第一个子串。但题目和用例库都没涉及该项检查，抛砖引玉，希望各路大神改进这代码。
m = m+2
t = i#记录i的值
elif i-m >= 0 and s[i-m:i+1] == s[i-m:i+1][::-1]:
m = m+1
t = i
if m > 0 and m%2 == 0:
return s[t-m+1:t+1]
elif m > 0 and m%2 != 0:
return s[t-m+1:t+1]

编辑于 2021-12-28 11:42:55 回复(1)