[LeetCode]5.Longest Palindromic Substring

题目

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

思路一

即不使用技巧，穷举所有可能。时间复杂度为O(n^3)（时间上最长，不推荐使用），空间复杂度为O(1)。本思路是从最大长度的字串开始，而不是从最小开始。假如说给定的字符串为size，先遍历长度为size的字串是否为回文串，如果是停止，如果不是遍历长度为size-1的字串是否是回文串，一次类推。

代码一

/*---------------------------------------
*   日期：2015-08-28
*   作者：SJF0115
*   题目: 5.Longest Palindromic Substring
*   网址：https://leetcode.com/problems/longest-palindromic-substring/
*   结果：Time Limit Exceeded
*   来源：LeetCode
-----------------------------------------*/
#include <iostream>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int size = s.size();
        //遍历字串的长度 从最大长度开始
        for(int i = size;i > 0;--i){
            //遍历字串的起始位置
            for(int start = 0;start + i <= size;++start){
                bool result = IsPalindromeSubNumber(s.substr(start,i));
                if(result){
                    return s.substr(start,i);
                }//if
            }//for
        }//for
        return "";
    }
private:
    //是否是回文串
    bool IsPalindromeSubNumber(string num){
        int len = num.length();
        for(int i = 0,j=len-1;i < j;i++,j--){
            if(num[i] != num[j]){
                return false;
            }
        }
        return true;
    }
};

int main(){
    Solution s;
    string num = "flsuqzhtcahnyickkgtfnlyzwjuiwqiexthpzvcweqzeqpmqwkydhsfipcdrsjkefehhesubkirhalgnevjugfohwnlhbjfewiunlgmomxkafuuokesvfmcnvseixkkzekuinmcbmttzgsqeqbrtlwyqgiquyylaswlgfflrezaxtjobltcnpjsaslyviviosxorjsfncqirsjpkgajkfpoxxmvsyynbbovieoothpjgncfwcvpkvjcmrcuoronrfjcppbisqbzkgpnycqljpjlgeciaqrnqyxzedzkqpqsszovkgtcgxqgkflpmrikksaupukdvkzbltvefitdegnlmzeirotrfeaueqpzppnsjpspgomyezrlxsqlfcjrkglyvzvqakhtvfmeootbtbwfhqucbnuwznigoyatvkocqmbtqghybwrhmyvvuchjpvjckiryvjfxabezchynfxnpqaeampvaapgmvoylyutymdhvhqfmrlmzkhuhupizqiujpwzarnszrexpvgdmtoxvjygjpmiadzdcxtggwamkbwrkeplesupagievwsaaletcuxtpsxmbmeztcylsjxvhzrqizdmgjfyftpzpgxateopwvynljzffszkzzqgofdlwyknqfruhdkvmvrrjpijcjomnrjjubfccaypkpfokohvkqndptciqqiscvmpozlyyrwobeuazsawtimnawquogrohcrnmexiwvjxgwhmtpykqlcfacuadyhaotmmxevqwarppknoxthsmrrknu";
    cout<<s.longestPalindrome(num)<<endl;
    return 0;
}

思路二

假设现在已经遍历到第 i 个字符，要找出以该字符为“中心”的最长对称字符串，我们需要用另两个指针分别向前和向后移动，直到指针到达字符串两端或者两个指针所指的字符不相等。因为对称子字符串有两种情况，所以需要写出两种情况下的代码：
（1） 第 i 个字符是该对称字符串的真正的中心，也就是说该对称字符串以第 i 个字符对称， 比如： “aba”
（2）第 i 个字符串是对称字符串的其中一个中心。比如“abba”。
所以遍历到每个字符都要考虑两种情况，它可能是在奇数个回文串中或者是在偶数个回文串中

代码二

/*---------------------------------------
*   日期：2015-08-28
*   作者：SJF0115
*   题目: 5.Longest Palindromic Substring
*   网址：https://leetcode.com/problems/longest-palindromic-substring/
*   结果：AC
*   来源：LeetCode
*   博客：
-----------------------------------------*/
#include <iostream>
using namespace std;

class Solution {
public:
    string longestPalindrome(string str) {
        int Max = 0,startIndex = 0;
        int size = str.size();
        int left,right;
        // 遍历字符串,以str[i]为子回文串的中心
        for(int i = 0;i < size;i++){
            //奇数字串
            int oddLen = 1;
            left = i-1;
            right = i+1;
            // 以str[i]为单独中心点的回文串 aba
            while(left >= 0 && right < size && str[left] == str[right]){
                left--;
                right++;
                oddLen += 2;
            }//while
            //更新最大长度
            if(oddLen > Max){
                Max = oddLen;
                //记录当前最大回文串的起始位置
                startIndex = left+1;
            }//if
            //偶数字串
            left = i;
            right = i+1;
            int evenLen = 0;
            // 以str[i]str[i+1]为中心点的回文串 abba
            while(left >= 0 && right < size && str[left] == str[right]){
                left--;
                right++;
                evenLen += 2;
            }//while
            //更新最大长度
            if(evenLen > Max){
                Max = evenLen;
                //记录当前最大回文串的起始位置
                startIndex = left+1;
            }//if
        }//for
        return str.substr(startIndex,Max);
    }
};

int main(){
    Solution s;
    string num = "abbad";
    cout<<s.longestPalindrome(num)<<endl;
    return 0;
}

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>