题目描述

给定一个字符串 s ，找到 s 中最长的回文子串。

假设 s 的最大长度为 1000。

示例

输入
- 输入一个字符串 s
输出
- 输出 s 中最长的回文字串

示例 1

输入：
babad

输出：
bab

示例 2

输入：
cbbd

输出：
bb

题解

dp[i][j] 表示字符串从 j 到 i 是否是为回文串，即当 s[j] == s[i] 如果 dp[i-1][j+1] 也是回文串，那么字符串从 j 到 i 也是回文串，即 dp[i][j] 为真。

代码

#include <iostream>
#include <string>

using namespace std;

int main() 
{
	string s = "";
	cin >> s;
	bool dp[1001][1001] = {0};
	int st = 0;
	int max = 1;
	for (int i = 0; i < s.size(); ++i) 
	{
		dp[i][i] = 1;
	}
	for (int i = 0; i < s.size() - 1; ++i) 
	{
		if (s[i] == s[i + 1]) 
		{
			dp[i][i + 1] = 1;
			max = 2;
			st = i;
		}
	}
	for (int len = 3; len <= s.size(); ++len) 
	{
		for (int i = 0; i + len <= s.size(); ++i) 
		{
			if (s[i] == s[i + len - 1] && dp[i + 1][i + len - 2] == 1) 
			{
				dp[i][i + len - 1] = 1;
				if (len > max) 
				{
					max = len;
					st = i;
				}
			}
		}
	}
	cout << s.substr(st, max);
	return 0;
}

返回顶部