leecode第五题（最长回文子串）

class Solution {
public:
    string longestPalindrome(string s) {

        int len = s.length();
        if (len == 0 || len == 1)
            return s;

        int index = 0, max_num = 1;

        for (int i = 1; i < len; i++)//检测奇数上的左右是否相同，例如aba，以b为中心
        {
            int t = i - 1, tt = i + 1, cur_num = 0;
            while (t >= 0 && tt < len && s[t] == s[tt])//我之前把s[t] == s[tt]放开始判断，但是遇到t=-1会报错，为了解决，先判断t》=0
            {
                cur_num = tt - t + 1;
                if (cur_num > max_num)
                {
                    index = t;
                    max_num = cur_num;
                }
                t--;
                tt++;
            }
        }

        for (int i = 0; i < len; i++)//检测偶数位上的左右是否相同，例如baab，以aa开始扩展
        {
            int t = i, tt = i + 1, cur_num = 0;
            while (t >= 0 && tt < len && s[t] == s[tt])
            {
                cur_num = tt - t + 1;
                if (cur_num > max_num)
                {
                    index = t;
                    max_num = cur_num;
                }
                t--;
                tt++;
            }
        }

        return s.substr(index, max_num);

    }
};

 

分析：

开始时候想到的是另一种动态规划法：开始时从头遍历每个字符，在每个字符开始时，设置一个尾指针从尾到头遍历，若二者相同，就判断这俩内部是不回文（写个小循环即可）。这个虽然写了三个循环，但是循环条件可以加上“当前两个指针距离大不大于最大的回文子串长度”，若小于，即便是回文也没必要判断了，这样一来虽然时间复杂度一样，但是节省很多啊，不过运行提醒我stack不足。。一开始我以为我想错了要不就是三个循环炸了，就看了题解的思想写成这个，但是后来我想应该是写错了，因为好像是s[t] == s[tt]放开始判断引起的问题（leecode的error提示真扯淡，和vs不一样），尴尬。