首页 > 试题广场 >

构造回文

[编程题]构造回文
  • 热度指数：36646 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。

输入描述:

输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.


输出描述:

对于每组数据，输出一个整数，代表最少需要删除的字符个数。
示例1

输入

abcda
google

输出

2
2
算法知识视频讲解
开通博客
头像 大厂算法岗必拿下
发表于 2021-09-05 04:08:36
把原来的序列倒过来。计算最长公共子序列。 然后该字符串得长度减去最长公共子序列的长度即可。 #include<bits/stdc++.h> using namespace std; char a[1001], b[1001]; int dp[1001][1001];//公共最长子序列 展开全文
去ta的博客 赞 (4) 回复(0) 收起

问题信息

动态规划
来自：腾讯2017暑期实习生编程题
难度：
168条回答 55429浏览

热门推荐

通过挑战的用户

相关试题

构造回文

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号