【leetcode刷题笔记】005.Longest Palind

日期：20180911

题目描述：

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Examples 1：

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Examples 2：

Input: "cbbd"
Output: "bb"

详解：

这道题我很机智的想出了从中间往两边找的方法，这样最坏时间复杂度就是O(n^2)。但是一开始做的时候没有想到长度为偶数的回文字符串。并且我一开始定义了一个i和j，两边就是i-j和i+j。这样到了偶数长度的回文字符串就非常麻烦，不如定义一个左指针j一个右指针k。这种时候不要嫌定义的变量多。下面是我的代码：

class Solution {
public:
    string longestPalindrome(string s) {
        int start=0,maxlen=1;
        for(int i=0;s[i]!='\0';i++){
            int j = i - 1,k = i + 1;
            while(j>=0&&s[k]!='\0'&&s[j]==s[k]){
                j--;
                k++;
            }
            if(k-j-1>maxlen){
                maxlen=k-j-1;
                start = j+1;
            } 
        }
        for(int i=0;s[i]!='\0';i++){
            int j = i,k = i + 1;
            while(j>=0&&s[k]!='\0'&&s[j]==s[k]){
                j--;
                k++;
            }
            if(k-j-1>maxlen){
                maxlen=k-j-1;
                start = j+1;
            } 
        }
        return s.substr(start,maxlen);
    }
};

这次终于击败了70%的C++使用者。

然后看了一下比我速度快的代码，如下所示：

class Solution {
public:
    string longestPalindrome(string s) {
        int start = 0; int maxLen = 0;
        int l = 0, r = 0;
        for(int i = 0; i < s.size();) {
            l = r = i;
            while(r < s.size() - 1 && s[r] == s[r + 1])
                r++;
            i = r + 1;
            while(l > 0  && r < s.size() - 1 && s[l - 1] == s[r + 1]) {
                l--;
                r++;
            }
            int len = r - l + 1;
            if(len > maxLen) {
                start = l;
                maxLen = len;
            }
        }
        return s.substr(start, maxLen);
    }
};

他的代码中，如果遇到非常多重复的字母（包括两个），会直接把这些字母视为一个，例如"cbbbbbbbefgh"最后l指针会是指向最左边的"b"，r指针会指向最右边的"b"，然后让i等于r+1这样下次就直接从e开始，这样一并解决了奇偶回文的问题，还在有很多连续重复字符的时候节省了时间。

妙啊！妙啊！