专栏首页AI那点小事2016年腾讯笔试题——构造回文

2016年腾讯笔试题——构造回文

给定一个字符串s,你可以从中删除一些字符,使得剩下的串是一个回文串。如何删除才能使得回文串最长呢? 输出需要删除的字符个数。

输入描述:

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

输出描述:

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

输入例子: abcda google

输出例子: 2 2


解题思路: 其实这是最长公共子序列的变种,先求出原字符串与反转串的最长公共子序列的长度,之后用原串长度减去即可。


Java代码如下:

import java.util.Scanner;
import java.lang.Math;

public class Main {
    static int[][] dp = new int[1010][1010];

    public static int GetMax(String str){
        StringBuffer buf = new StringBuffer();
        String reverse = buf.append(str).reverse().toString();
        int len = str.length();
        for ( int i = 1 ; i <= len ; i++){
            for ( int j = 1 ; j <= len ; j++){
                if ( str.charAt(i-1) == reverse.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[len][len];
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String str;
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            str = in.next();
            System.out.println(str.length() - GetMax(str));
        }
        in.close();
    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 构造回文

    给定一个字符串s,你可以从中删除一些字符,使得剩下的串是一个回文串。如何删除才能使得回文串最长呢? 输出需要删除的字符个数。

    AI那点小事
  • 最长公共连续子串

    牛牛有两个字符串(可能包含空格),牛牛想找出其中最长的公共连续子串,希望你能帮助他,并输出其长度。 输入描述: 输入为两行字符串(可能包含空格),长度...

    AI那点小事
  • 剑指offer--跳台阶

    一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

    AI那点小事
  • 构造回文

    给定一个字符串s,你可以从中删除一些字符,使得剩下的串是一个回文串。如何删除才能使得回文串最长呢? 输出需要删除的字符个数。

    AI那点小事
  • ​LeetCode刷题实战62:不同路径

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • 打卡群刷题总结0923——完全平方数

    链接:https://leetcode-cn.com/problems/perfect-squares

    木又AI帮
  • 【leetcode刷题】T164-完全平方数

    给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

    木又AI帮
  • [Leetcode][python]Unique Paths/Unique Paths II

    动态规划 由于只能有向下向右,只有从[1][1]开始的格子需要选择走法,第一行和第一列所有都只有一种走法,所有都设置成1,(这里图方便所有都初始化为1),然...

    后端技术漫谈
  • Leetcode【120、611、813、915】

    容易想到用动态规划求解,dp[i][j] 存储累加到位置 (i, j) 的最小路径和。

    echobingo
  • PTA 7-2 列车调度(25 分)

    7-2 列车调度(25 分) 火车站的列车调度铁轨的结构如下图所示。 ? 两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平...

    Kindear

扫码关注云+社区

领取腾讯云代金券