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.

题意寻找并输出字符串中的最长回文串。

 

 

 

没想到什么特别好的算法，就上暴力加些剪枝。

 

枚举回文串的长度，从最长的开始，寻找是否有当前长度的回文串。

 

如果找到，直接弹出循环，没找到就减小回文串的长度。

 

l记录满足条件的回文串在原串中的下标，r记录回文串的长度。

 

 

class Solution {  
public:  
    string longestPalindrome(string s) {  
        int i,j,k,len=s.length(),l=0,r=1;  
        for(k=len;k>=2;--k)  
        {  
            for(i=0;i+k<=len;++i)          
            {  
                for(j=0;j<k/2;++j)  
                {  
                    if(s[i+j]!=s[i+k-j-1])break;  
                }  
                if(j!=k/2)continue;  
                else  
                {  
                    l=i;r=k;  
                }  
            }  
            if(r==k)break;  
        }  
          
        string temp;  
        return temp.assign(s,l,r);  
    }  
};  

 

 

 

补充：软件开发 , C++ ,