题目地址

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-palindromic-substring/ (opens new window)

题目描述

给定一个字符串 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

提交结果