力扣5.最长回文子串（暴力解法)

题目描述

题目链接5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

思路解析

        首先我们可以直接封装一个判断是否为回文的函数，参数为一个字符串即可，函数内进行循环，从头和尾向中间遍历，当有不相同时返回false，遍历完成之后返回true。

        因为我们要找到的是最长的回文子串，所以我们从最长的子串开始判断，找到回文子串时直接返回，不需要再进行之后的判断，具体步骤为：

 一层循环：创建一个变量len为字符串长度（最长子串长度），一直遍历到len比1大，如果len遍历到1了的话，说明该字符串任意一个字符都可以为最长回文子串

二层循环：i从头开始遍历，判断从i开始长度为len的子串是否为回文子串，如果是直接返回。这里可以进行一个小优化，如果该子串的第一个字符和最后一个字符不相等的话，就不用进入判断回文函数了，可以有效应对大量数据。

如果遍历完都没有找到则返回第一个字符。

代码实现

class Solution {
public:bool torf(string s){//判断是不是回文字符串for(int i=0,j=s.size()-1;i<j;i++,j--){if(s[i]!=s[j])return false;}return true;}string longestPalindrome(string s) {for(int len=s.size();len>1;len--){//从最长子串开始判断for(int i=0;i+len<=s.size();i++){//从头开始遍历，如果从i开始len长度的子串存在进入判断if(s[i]!=s[i+len-1])continue;//小优化，如果头尾不同不进入判断if(torf(s.substr(i,len)))return s.substr(i,len);//如果是直接返回，不用判断更短的子串了}}string ans;//如果没有找到回文子串，返回第一个字符ans+=s[0];return ans;}
};