标签搜索

目 录CONTENT

文章目录

腾讯--构造回文.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 4 阅读 / 1,903 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

腾讯--构造回文

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

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

0

评论区