5. 最长回文子串

“回文”是指正读反读都能读通的句子。设n是一任意自然数,若将n的各位数字反向排列所得自然数n1与n相等,则称n为一回文数。例如,若n=1234321就是回文数

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() < 2) return s;//s中只有一个元素
        int left = 0, right = 0, start = 0, maxLen = 0;
        for (int i = 0; i < s.size(); i++) {
            searchPalindrome(s, i, i, start, maxLen);
            searchPalindrome(s, i, i +1, start, maxLen);
        }
        return s.substr(start, maxLen);
    }

    void searchPalindrome(string s, int left, int right, int&start, int&maxLen) {
        while((left >= 0) && (right < s.size()) && (s[left] == s[right])) {
            left--;
            right++;
        }
        //如果得到的回文数的大小比之前的大,就更新maxLen
        if (maxLen < right - left + 1 -2) {
            maxLen = right - left + 1 - 2;//right -left + 1是得到的数组长度,因为之前执行了left--和right ++,所以再减去2
            start = left + 1;
        }

    }
};

上一篇:每日一题 0201


下一篇:java数据结构:插入排序