[LeetCode]5.Longest Palindromic Substring-阿里云开发者社区

开发者社区> 云计算> 正文

[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;
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章