最大回文子串——暴力法

题目描述

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

示例 1：

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

输入：s = "cbbd"
输出："bb"
示例 3：

输入：s = "a"
输出："a"
示例 4：

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

提示：

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

思路

首先将长度为1和2的特殊考虑

对于长度超过2的字符串，通过两个循环，从字符串的开头和字符串的结尾开始走起，一旦发现两个字符相同的，继续两边向中间走，一旦出现不同证明不是回文。

注意：

1. 以字符串的第一个字符初始化结果
2. 设置flag，一旦出现不同字符，证明不是回文，跳出循环
3. 如果两边的 i , j 游标的距离没有当前的res长就不用继续查看

代码

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size() <= 2){
            if (s[0] == s[s.size()-1]){
                return s;
            } else{
                return s.substr(0, 1);
            }
        }

        string result = s.substr(0, 1);
        for(int i=0; i<s.size(); i++){
            for(int j=s.size()-1; j>0; j--){
                int flag = 1;
                if (j-i+1 <= result.size()){
                    break;
                }

                if(s[i] == s[j]){
                    int temp_i = i + 1;
                    int temp_j = j - 1;
                    while (temp_i < temp_j){
                        if (s[temp_i] != s[temp_j]){
                            flag = 0;
                            break;
                        }
                        temp_i ++;
                        temp_j --;
                    }
                    if(flag){
                        string temp_res = s.substr(i, j-i+1);                        
                        if(temp_res.size() > result.size()){
                            result = temp_res;
                            break;
                        }
                    }
                }
            }
        }
        return result;
    }