Skip to content

5. Longest Palindromic Substring

难度:Medium

刷题内容

原题连接

  • https://leetcode.com/problems/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.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

解题方案

思路 1 **- 时间复杂度: O(N^2)*- 空间复杂度: O(N^2)***

这题如果用单纯暴力的解法,时间复杂度为 O(n ^ 3),肯定超时,那么就要对这个算法进行优化,这里采用的是DP思想,定义 p(i,j)为s中的第i个数到s中的第j个数的子串,不难看出 p(i,j)中的子串有重复计算,接下来就可以写出状态转移方程 P(i,j)=(P(i+1,j?1) and S[i] == S[j])

class Solution {
public:
    int dp[1000][1000] = {0};
    string longestPalindrome(string s) {
         int beg = 0,en = 1,ans = 0;
        int length = s.length();
        for(int i = 0;i < length;++i)
        {
            dp[i][i] = 1;
            if(i + 1 < length && s[i] == s[i + 1])
                dp[i][i + 1] = 1;
        }
        for(int i = 0;i < length;++i)
            for(int j = 0;j <= i;++j)
            {
                if(i > j + 1)
                    dp[j][i] = (dp[j + 1][i - 1] && s[i] == s[j]);
                if(dp[j][i] && i - j + 1 > ans)
                {
                    ans = i - j + 1;
                    beg = j;
                    en = i + 1;
                }
            }
        string ret(s.begin() + beg,s.begin() + en);
        return ret;
        }
};


回到顶部