最长回文子串

问题描述
给你一个字符串s,找到s中最长的回文子串

示例1:
输入:s = "babad"
输出:"bab"

示例2:
输入:s = "cbbd"
输出:"bb"
解题思路:

https://www.bilibili.com/video/BV1SE411y7RW?from=search&seid=2950817619903450615

https://www.bilibili.com/video/BV124411X7Ly?from=search&seid=18362855079906693150

方法一:

#include<iostream>
#include <string.h>
#include<string>
using namespace std;

int main()
{
	string s;

	cin>>s;

	if(s.size() == 0 || s.size() < 2) //一个字符也是回文字符
		cout<<s;

	int max = 0;
	string ret = " ";

	for(int i = 0;i < s.size();i++)
	{
		for(int j =1;j < s.size();j++)
		{
			string tmp = s.substr(i,j-i+1);//substr:复制子字符串,包含s中从i开始的j-i+1个字符的拷贝
			string tmpr(tmp);//将字符串翻转与原字符串对比
			reverse(tmp.begin(),tmp.end());//字符串进行反向排序

			if(tmp == tmpr && tmpr.size() > max)
			{
				max = tmp.size();
				ret = s.substr(i,j-i+1);
			}
		}
	}
	cout<<ret<<endl;
	return 0;
}

其他方法后续更新

最长回文子串

上一篇:Scala基础


下一篇:perl 正则表达式