最长回文子串算法题解C/C++/JAVA/Python

题目:

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

示例 1:

输入:"babad"

输出:"bab"

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

示例 2:

输入: "cbbd"

输出: "bb"

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/longest-palindromic-substring

C解法:


int max(int a, int b)
{
    return a > b ? a : b;
}
char *substr(char *s, int begin, int end)
{
    char temp[end - begin + 1];
    char *string = NULL;
    if (strlen(s) < 2 || begin < 0 || begin >= end)
    {
        return s;
    }
    for (int i = begin; i < end; i++)
    {
        temp[i - begin] = s[i];
    }
    temp[end - begin] = '\0';
    string = temp;
    return string;
}
int expandCenter(char *s, int left, int right)
{
    int n = strlen(s);
    int l = left, r = right;
    while (l >= 0 && r < n && s[l] == s[r])
    {
        l--;
        r++;
    }
    return r - l - 1;
}
char *longestPalindrome(char *s)
{
    int n = strlen(s);
    if (n == 0)
    {
        char *a = "";
        return a;
    }
    int start = 0, end = 0;
    int len1 = 0, len2 = 0, len3 = 0;
    for (int i = 0; i < n; i++)
    {
        len1 = expandCenter(s, i, i);
        len2 = expandCenter(s, i, i + 1);
        len3 = max(len1, len2);
        if (len3 > end - start)
        {
            start = i - (len3 - 1) / 2;
            end = i + len3 / 2;
        }
    }
    return substr(s, start, end + 1);
}

C++解法:


class Solution
{
public:
    int expandCenter(string s, int left, int right)
    {
        int l = left, r = right;
        while (l >= 0 && r < s.length() && s[l] == s[r])
        {
            l--;
            r++;
        }
        return r - l - 1;
    }
    string longestPalindrome(string s)
    {
        if (s.empty())
        {
            return "";
        }
        int start = 0, end = 0;
        int len1 = 0, len2 = 0, len3 = 0;
        for (int i = 0; i < s.length(); i++)
        {
            len1 = expandCenter(s, i, i);
            len2 = expandCenter(s, i, i + 1);
            len3 = max(len1, len2);
            if (len3 > end - start)
            {
                start = i - (len3 - 1) / 2;
                end = i + len3 / 2;
            }
        }
        return s.substr(start, end - start + 1);
    }
};

JAVA解法:


class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandCenter(s, i, i);
            int len2 = expandCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end+1);
    }

    private int expandCenter(String s, int left, int right) {
        int n = s.length();
        int l = left, r = right;
        while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return r - l - 1;
    }
}

Python3解法:


class Solution:
    def longestPalindrome(self, s: str) -> str:
        start, end, n = 0, 0, len(s)
        if (not s) or (n < 1):
            return ""
        for i in range(n):
            len1 = self.expandCenter(s, i, i)
            len2 = self.expandCenter(s, i, i + 1)
            len3 = max(len1, len2)
            if len3 > (end - start):
                start = i - (len3 - 1) // 2
                end = i + len3 // 2
        return s[start : end + 1]

    def expandCenter(self, s: str, left: int, right: int):
        l, r, n = left, right, len(s)
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return r - l - 1
 
共 0 条评论