leetcode 5 最长回文子串

 搞暴力算法也能搞出来,而且不大困难,这个题最主要的问题是第一次接触了动态规划的东西,具有一定的历史意义。下面先贴暴力代码

class Solution 
{
public:
    string longestPalindrome(string s) 
    {
        int n = s.length();
        int i = 0;
        int j = n-1;
        int maxSize = 1;
        string maxString = s.substr(0,1);
        for(i = 0 ; i < n-1  ; i++)
        {
            for(j = n-1 ; j > i ; j--)
            {
                if(s[i] == s[j])
                {
                    int k = 0;
                    while(s[i+k] == s[j-k] && i+k<j-k)
                    {
                        k++;
                    }
                    if(i+k == j-k || i+k == j-k+1)
                    {
                        if(i == 0 && j == n-1)
                        return s;                       
                        else if(j-i+1 > maxSize)
                        {
                            maxSize = j-i+1;
                            cout<<maxSize<<endl;                   
                            maxString= s.substr(i,j-i+1);
                        }
                    
                    }
                }
            }          
        
        }
        return maxString;
    }
};

下面是动态规划代码

上一篇:数学问题04 素数


下一篇:5, java数据结构和算法: 栈