腾讯--构造回文

@[toc]

一、题目描述

给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？

输出需要删除的字符个数。

•  输入描述:

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

•  输出描述:

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


输入例子1:
abcda
google

输出例子1:
2
2

二、分析

这道题其实和：最⻓公共⼦序列：最⻓公共⼦序列问题解法相似。

•  为了和最⻓公共⼦序列这道题一致，我们先用已知字符串构造一个新的字符串并翻转一下（翻转目的是：如果对应位置相等，就说明满足回文关系），那么s1和s2就构成两个字符串，而题目中要求我们删除字符串使剩下的字符串构成最长的回文串，那么我们是否可以理解为求两个字符串中最长的公共子序列呢？

//s1就是已知的字符串
string s2(s1);
reverse(s2.begin(),s2.end());

•  首先题目求的是回文序列，那么s2是s1翻转过来的，那么如果满足回文关系，那么对应相同位置上的字符肯定是相等的，是不是对应最长公共子序列当中的公共
•  同理，题目中要求是删除字符使s1和s2构成最长的回文串，那么是否就对应着最长公共子序列当中的序列（串：字符之间必须连续；序列：可以不连续）。
•  所以这道题可以借鉴最长回味子序列的解法，这里我们在写一遍
•  这道题可以用dp数组求解；同样是套路；动态规划的第一步：明确状态和选择，对于这道题来说，状态就是回文串的长度，选择就是是否删除某个字符
•  所以对于dp数组来说含义就明确了：dp[i][j]：对于 s1[1…i] 和 s2[1…j] ，它们的 最长回文字串的⻓度是 dp[i][j]
•  第⼆步， 定义 base case
•  我们专门让索引为 0 的⾏和列表⽰空串， dp[0][…] 和 dp[…][0] 都应该初始化为 0， 这就是 base case。
•  ⽐如说， 按照刚才 dp 数组的定义， dp[0][3]=0 的含义是： 对于字符串"" 和 “bab” ， 其最长回文字串的⻓度是 0。 因为有⼀个字符串是空串， 它们的最长回文字串的⻓度是显然应该是 0
•  第三步， 找状态转移⽅程。
•  状态转移说简单些就是做选择， ⽐如说这个问题， 是求 s1 和 s2 的最长回文字串的⻓度是， 不妨称这个⼦序列为 lcs 。 那么对于 s1 和 s2 中的每个字符， 有什么选择？
•  很简单， 两种选择， 要么在 lcs 中， 要么不在
•  这个「在」 和「不在」 就是选择， 关键是， 应该如何选择呢？
•  这个需要动点脑筋： 如果某个字符应该在 lcs 中， 那么这个字符肯定同时存在于 s1 和s2 中， 因为 lcs 是最长回文字串嘛。
•  所以本题的思路是这样：
•  ⽤两个指针 i 和 j 从后往前遍历 s1 和 s2 ， 如果 s1[i]==s2[j] ， 那么这个字符⼀定在 lcs 中； 否则的话， s1[i] 和 s2[j] 这两个字符⾄少有⼀个不在 lcs 中， 需要丢弃⼀个。
•  分析完就可以整代码了

三、代码

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

const int MAXN=1010;
int dp[MAXN][MAXN];

//先求s的反串reverse，然后求他们的最长的公共子序列，要删除的字符个数就能知道
//时间复杂度O(N^2)

int getRemoveNumber(string &s1)
{
    string s2(s1);
    reverse(s2.begin(),s2.end());
    
    int len=s1.length();
    memset(dp,0,sizeof dp);//讲二维数组全部替换成0
    
    for(int i=0;i<len;++i)
    {
        for(int j=0;j<len;++j)
        {
            if(s1[i]==s2[j])
                //判断如果遍历到相等的字符，
                dp[i+1][j+1]=dp[i][j]+1;
            else 
                dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
        }
    }
    return len-dp[len][len];
}

int main()
{
   string s;
   while(cin>>s)
   {
       cout<<getRemoveNumber(s)<<endl;
   }
   return 0;
}
 

当然可以用备忘录优化一下！！！