题目

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

原题链接

解题思路

最长回文字串，相信做过Palindrome Partitioning II 这个题的同学应该可以很快做出来。没错，这个题还可以使用动态规划方法得到一个时间复杂度为O(n^2)的解法，当然如果你想要更好的时间复杂度的算法也是有的。好的，我们先来看看时间复杂度为O(n^2)的算法。

代码实现

代码一--动态规划O(n^2)

相信如果你在网上看过了别人的算法，你会发现我的算法是最简洁的。哈哈，这个题需要注意的是如果你用惯了vector的话，你这里肯定会得到超时的提示。

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if(n<=1) return s;
        bool dp[1000][1000]= {false,false};
        int begin =0, max = 0;
        for(int i=n-1; i>=0; --i){
            for(int j=i; j<n; ++j){
                if(s[i] != s[j]) continue;
                if(j-i<2 || dp[i+1][j-1]==true){
                    dp[i][j] = true;
                    if(j-i > max){
                        begin = i;
                        max = j-i;
                    }
                }
            }
        }
        
        return s.substr(begin, max+1);
    }
};

代码二--时间复杂度为O(n)的解法

这个我专门有篇博客介绍《Longest Palindromic Substring-----最长回文子串 》，点击阅读。