LeetCode 第五题:最长回文子串

题目地址

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-palindromic-substring/

题目描述

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

个人解题思路

暴力解法比较简单,直接两层循环遍历所有可能,判断是否为回文,取最大那一个就好了。

个人在此基础上的优化:每个回文都有一个中心,这个中心可能是一个字符,也可能是两个字符,只要求各个中心的最长回文就可以了。由于回文串中间的子串也是回文子串,一旦子串不是回文,那么该中心更长的子串也不是回文。

解题代码 Java

class Solution {
    public String longestPalindrome(String s) {

        if (s.length() <= 1) return s;
        if (s.length() == 2) return s.charAt(0)==s.charAt(1)?s: String.valueOf(s.charAt(0));

        int max = 0;
        String maxString = "";

        for (int index = 1; index < s.length(); index++) {
            int centerLeft = index - 1, doubleLeft = index - 1, centerRight = index + 1, doubleRight = index;
            int centerLength = 1, doubleLength = 1;
            boolean centerNext = true, doubleNext = true;

            while (centerNext || doubleNext) {

                if (centerLeft >= 0 && centerRight < s.length() && s.charAt(centerLeft) == s.charAt(centerRight)) {
                    centerRight++;
                    centerLeft--;
                } else {
                    centerLength = centerRight - centerLeft - 1;
                    centerNext = false;
                }

                if (doubleLeft >= 0 && doubleRight < s.length() && s.charAt(doubleLeft) == s.charAt(doubleRight)) {
                    doubleRight++;
                    doubleLeft--;
                } else {
                    doubleLength = doubleRight - doubleLeft - 1;
                    doubleNext = false;
                }
            }

            if (centerLength > max) {
                max = centerLength;
                maxString = s.substring(centerLeft+1, centerRight);
            }

            if (doubleLength > max) {
                max = doubleLength;
                maxString = s.substring(doubleLeft+1, doubleRight);
            }
        }

        return maxString;
    }
}

解题代码 Go

func longestPalindrome(s string) string {

    if len(s) <= 1 {
        return s
    } else if len(s) == 2 {
        return map[bool]string{true: s, false: s[:1]}[s[0] == s[1]]
    }

    max := 0
    maxString := ""

    for index := 1; index < len(s); index++ {
        centerLeft, centerRight, doubleLeft, doubleRight := index-1, index+1, index-1, index
        centerLength, doubleLength := 1,1
        centerNext, doubleNext := true, true

        for centerNext || doubleNext {
            if centerLeft >= 0 && centerRight < len(s) && s[centerLeft]==s[centerRight] {
                centerLeft --
                centerRight ++
            }else {
                centerLength = centerRight - centerLeft -1
                centerNext = false
            }

            if doubleLeft >= 0 && doubleRight < len(s) && s[doubleLeft]==s[doubleRight] {
                doubleLeft --
                doubleRight ++
            }else {
                doubleLength = doubleRight - doubleLeft -1
                doubleNext = false
            }
        }

        if centerLength > max {
            max = centerLength
            maxString = s[centerLeft+1: centerRight]
        }

        if doubleLength > max {
            max = doubleLength
            maxString = s[doubleLeft+1: doubleRight]
        }

    }

    return maxString
}

解题代码 Python

class Solution:

    def longestPalindrome(self, s: str) -> str:

        if len(s) <= 1: return s
        if len(s) == 2: return s if s[0] == s[1] else s[:1]

        max = 0
        max_string = ""

        for index in range(1, len(s)):
            center_left, center_right, double_left, double_right = index - 1, index + 1, index - 1, index
            center_length, double_length = 1, 1
            center_next, double_next = True, True

            while center_next or double_next:
                if center_left >= 0 and center_right < len(s) and s[center_left] == s[center_right]:
                    center_left -= 1
                    center_right += 1
                else:
                    center_length = center_right - center_left - 1
                    center_next = False


                if double_left >= 0 and double_right < len(s) and s[double_left] == s[double_right]:
                    double_left -= 1
                    double_right += 1
                else:
                    double_length = double_right - double_left - 1
                    double_next = False

            if center_length > max:
                max = center_length
                max_string = s[center_left+1: center_right]

            if double_length > max:
                max = double_length
                max_string = s[double_left+1: double_right]

        return max_string

提交结果

最长回文子串提交结果对比