0005._Longest_Palindromic_Substring.md

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;
		}
};