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.

解题思路：

1、动态规划，找回文。用二维数组记录j到i是否为回文，若isPalin[j+1][i-1]为回文，且s[j]==s[i]，则isPalin[j][i]为回文。

class Solution {
public:
    string longestPalindrome(string s) {
        string result="";
        int len=s.length();
        if(len==0){
            return result;
        }
        int start=0, end=0;
        bool isPalin[len][len];       //i到j是否为回文
        for(int i=0; i=0; j--){        //计算j到i是否为回文
                if( (j==i-1&&s[j]==s[i]) || (isPalin[j+1][i-1]&&s[j]==s[i])){
                    isPalin[j][i]=true;
                    if(i-j>end-start){
                        start=j;
                        end=i;
                    }
                }else{
                    isPalin[j][i]=false;
                }
            }
        }
        
        
        result = s.substr(start, end-start+1);
        
        return result;
    }
};

此前用某个编译器不支持int array[变量]，因此每次都用new，却会报内存溢出的错误。leetcode的编译器支持int array[变量]，可以通过。

2、上述方法空间复杂度为O(n^2)，时间复杂度为O(n^2)。若以某个字符（或字符的空隙）向两边扩展统计，可以将空间复杂度降为O(1)，下面是誊抄其他人的Java代码：

public String longestPalindrome(String s) {
    if(s == null || s.length()==0)
        return "";
    int maxLen = 0;
    String res = "";
    for(int i=0;i<2*s.length()-1;i++)
    {
        int left = i/2;
        int right = i/2;
        if(i%2==1)
            right++;
        String str = lengthOfPalindrome(s,left,right);
        if(maxLen=0 && right
二次刷题（2015-08-17）
class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.length();
        if(len == 0){
            return "";
        }
        string result = "";
        
        for(int i=0; i<2*len - 1; i++){
            int left = i/2;
            int right = i/2;
            if(i%2==1){
                right++;
            }
            while(left>=0 && right < len && s[left] == s[right]){
                left--;
                right++;
            }
            string temp = s.substr(left + 1, right - left - 1);
            if(temp.length() > result.length()){
                result = temp;
            }
        }
        
        return result;
    }
};

 
转载请注明： » [LeetCode] Longest Palindromic Substring

<!--
                    

                    	

                        	

                            	
                            
                        
                        

                        	

                            	
相关博文：
                                

                                	
                                    	
                                        	
                                        
                                        
定制桌面成功案例
                                    
                                    
                                    	
                                        	
                                        
                                        
海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）
                                    
                                    
                                    	
                                        	
                                        
                                        
汉字转拼音c/c++源码，支持gb2312和utf8
                                    
                                    
                                    	
                                        	
                                        
                                        
数据库顶级会议——SIGMOD介绍
                                    
                                
                            
                        
                    
                    -->