最长回文子串

描述

leetcode 官方第 5 题，给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

示例3:

输入：s = "a"
输出："a"

示例4:

输入：s = "ac"
输出："a"

提示：

1. 1 <= s.length <= 1000
2. s 仅由数字和英文字母（大写和/或小写）组成

思路

这题我们这里就简单粗暴的使用暴力计算的方法来实现，使用双重循环计算使用字符串的情况，并判断每一个字符串是否是回文字符串，如果是，并且长度大于当前最长回文字符串的长度，那么就保存结果。

判断是否是回文字符串，思想是使用两个指针分别指向字符串开始和结束，然后判断是否相等，如果相等，则继续左指针右移，右指针左移，如果不相等了，则表明不是回文字符串。如果相遇了还是相等，那说明是回文字符串。

比如，以我们示例一中的字符串 babad 为例，开始左右指针如下：

此时，我们直接判断 pLeft 指针指向的字符与 pRight 指向的字符不相等，因此，直接就返回不是回文字符串。现在，我们判断一个是回文字符串的，如下：

我们看到，此时 pLeft 指针指向的元素与 pRight 指针指向的元素相等，那么此时，我们继续右移 pLeft 指针，左移 pRight 指针，如下图：

我们看到，此时 pLeft 指针与 pRight 指针指向的元素还是相等的，因此，我们继续移动指针，如下图：

我们看到，此时 pLeft 指针与 pRight 指针已经重合了，因此，循环结束，即该字符串是回文字符串。

代码具体实现

Java语言版本

class Solution {
    public String longestPalindrome(String s) {
        int cnt = s.length();
        String result = "";
        //保存当前的最长子串的长度
        int maxlen = 0;
        //暴力循环
        for (int i = 0; i < cnt; i++){
            //内存循环从外层循环的下一个索引开始
            for (int j = i+1; j <= cnt; j++){
                //如果是回文，并且当前长度大于了最大长度，则赋值并更新
                if (isPalindromeStr(s.substring(i, j)) && j - i > maxlen){
                    result = s.substring(i, j);
                    maxlen = j - i;
                }
            }
        }
        return result;
    }
    //判断是否是回文字符串，思想是使用两个指针分别指向字符串开始和结束，然后判断是否相等
    //如果相等，则继续左指针右移，右指针左移
    //如果不相等了，则表明不是回文字符串
    //如果相遇了还是相等，那说明是回文字符串
    public boolean isPalindromeStr(String str){
        //左指针
        int left = 0;
        //右指针
        int right = str.length()-1;
        //循环的结束条件是左右指针重合
        while(left < right){
            //如果不相等了，则不是回文字符串，直接返回
            if (str.charAt(left) != str.charAt(right)){
                return false;
            }
            //左指针右移
            left++;
            //右指针左移
            right--;
        }
        //左右指针相遇了，还是相等，则表明是回文
       return true;
    }
}

Go语言版本

func longestPalindrome(s string) string {
	var(
		cnt = len(s)
		result = ""
		//保存当前的最长子串的长度
		maxlen = 0
	)
	//暴力循环
	for i := 0; i < cnt; i++{
		//内存循环从外层循环的下一个索引开始
		for j := i+1; j <= cnt; j++{
			if isPalindromeStr(s[i:j]){
				//如果是回文，并且当前长度大于了最大长度，则赋值并更新
				if j - i > maxlen{
					result = s[i:j]
					maxlen = j - i
				}
			}
		}
	}
	return result
}
//判断是否是回文字符串，思想是使用两个指针分别指向字符串开始和结束，然后判断是否相等
//如果相等，则继续左指针右移，右指针左移
//如果不相等了，则表明不是回文字符串
//如果相遇了还是相等，那说明是回文字符串
func isPalindromeStr(str string)(isPalindrome bool){
	var(
		//左指针
		left = 0
		//右指针
		right = len(str)-1
	)
	//循环的结束条件是左右指针重合
	for left < right{
		//如果不相等了，则不是回文字符串，直接返回
		if str[left] != str[right]{
			return
		}
		//左指针右移
		left++
		//右指针左移
		right--
	}
	//左右指针相遇了，还是相等，则表明是回文
	isPalindrome = true
	return
}