构造回文

Previous腾讯 2017 暑期实习生编程题 Next算法基础-字符移位

Last updated 5 years ago

Was this helpful?

构造回文

题目描述

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

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

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

输入例子:

abcdagoogle

输出例子:

参考资料

分析

对于这题来说，插入字符和删除字符使其成为回文串，答案是一样的.首先求s的反串rs，然后对s和rs求最长公共子序列，要删除的字符个数就是 LCS.

Python 解答

自己用 Python 写了，虽然结果正确，但是超时了。思路是用动态规划。

#!/bin/env python3
# -*- coding: utf-8 -*-
# version: Python3.X
"""
# 题目描述
给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？输出需要删除的字符个数。

# 参考资料
    http://www.voidcn.com/blog/Do_Know/article/p-5978576.html

# 分析
对于这题来说，插入字符和删除字符使其成为回文串，答案是一样的.

首先求s的反串rs，然后对s和rs求最长公共子序列，要删除的字符个数就是 LCS.
"""

__author__ = '__L1n__w@tch'

MAX_LENGTH = 1010  # 1 <= s <= 1000


# 答案用动态规划解决的
def dynamic_solve(s):
    """
    动态规划求取构造回文要删除的字符个数
        dp[i][j] 表示 s1 的前 i 个字符串, s2 的后 j 个字符串中的最大公共字串

    动态方程:
        dp[i + 1][j + 1] = dp[i][j] + 1 if s1[i] == s2[j] else max(dp[i][j + 1], dp[i + 1][j])
    :param s: 原始字符串
    :return: 需要删除的字符个数
    """
    # 先求反串
    length = len(s)
    reversed_s = s[::-1]

    # 求最长公共子序列
    dp = [[0 for i in range(MAX_LENGTH)] for i in range(MAX_LENGTH)]  # 初始化

    for i in range(length):
        for j in range(length):
            if s[i] == reversed_s[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 length - dp[length][length]  # 长度减去最长公共子序列即为所求


if __name__ == "__main__":
    tests = ["", "a", "ab", "abcda", "google",
             "zgtklhfzomzjckwmluvivvcmhjrwkuvcjrxojobpdedpamdshcwwsetfbacvonecrdvugeibglvhxuymjvoryqjwullvzglqazxrdmczyvbgakjagttrezmvrlptiwoqkrtxuroeqmryzsgokopxxdpbejmtwvpnaqrgqladdszhdwxfckmewhdvihgvacueqhvwvjxoitlpfrckxkuksaqzjpwgoldyhugsacflcdqhifldoaphgdbhaciixouavqxwlghadmfortqacbffqzocinvuqpjthgekunjsstukeiffjipzzabkuiueqnjgkuiojwbjzfynafnlcaryygqjfixaoeowhkxkbsnpsvnbxuywfxbnuoemxynbtgkqtjvzqikbafjnpbeirxxrohhnjqrbqqzercqcrcswojyylunuevtdhamlkzqnjrzibwckbkiygysuaxpjrgjmurrohkhvjpmwmmtpcszpihcntyivrjplhyrqftghglkvqeidyhtmrlcljngeyaefxnywpfsualufjwnffyqnpitgkkyrbwccqggycrvoocbwsdbftkigrkcbojuwwctknzzmvhbhbfzrqwzllulbabztqnznkqdyoqnrxhwavqhzyzvmmmphzxbikpharseywpfsqyybkynwbdrgfsaxduxojcdqcjuaywzbvdjgjqtoffasiuhvxcaockebkuxpiomqmtvsqhnyxfjceqevqvnapbk"]
    for each_test in tests:
        print(dynamic_solve(each_test))

C 语言版本 1

自己用 C 又重写了一遍，期望能通过，结果发现提示说答案错，同样的数据，在网上测试的时候结果错了，在本机测试的时候自己出来的答案是对的。说明不是代码问题，而是题目所给字符串的输入问题，尝试用文件读入数据解决结果发现还是没错，所以就不知道了。以下是代码：

//
// Created by w@tch on 16/7/21.
//

#include <stdio.h>
#include <string.h>

#define MAX_LENGTH 1001

char *strrev(char *s) {
    if (s == NULL || s[0] == '\0')
        return s;

    for (char t, *p = s, *q = s + strlen(s) - 1; p < q; p++, q--) {
        t = *p;
        *p = *q;
        *q = t;
    }

    return s;
}

int dynamic_solve(char *s) {
    // 先求反串
    char *reverse_s = new char(strlen(s) * sizeof(char));
    strcpy(reverse_s, s);
    strrev(reverse_s);

    // 初始化
    int length = strlen(s);
    int i, j;
    int dp[MAX_LENGTH][MAX_LENGTH] = {0};

    // 求最长公共子序列
    for (i = 0; i < length; ++i) {
        for (j = 0; j < length; ++j) {
            if (s[i] == reverse_s[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
            }
            else {
                dp[i + 1][j + 1] = dp[i][j + 1] > dp[i + 1][j] ? dp[i][j + 1] : dp[i + 1][j];
            }
        }
    }

    return length - dp[length][length]; // 长度减去最长公共子序列即为所求
}

int main(void) {
//    FILE *f = fopen("/Users/L1n/Desktop/C_C++ Projects/C_C_Plus_Plus_Knowledge/data.txt", "r");
    FILE *f = fopen("data.txt", "r");
    if (f != NULL) {
        char s[MAX_LENGTH] = {0};
        while (fscanf(f, "%s", s) != EOF) {
            printf("%d\n", dynamic_solve(s));
        }
    }


    return 0;
}

/* 提交用
int main() {
 char s[MAX_LENGTH] = {0};
 while (scanf("%s", s) != EOF) {
 printf("%d\n", dynamic_solve(s));
 }
}
*/

C 语言版本 2

为了通过，照着网上的答案又重新敲了一遍。这回提交正确了，最终代码如下：

// 构造回文, 解决方案 2, 思路一样都是动态规划, 不过用的库函数不一样
// Created by w@tch on 16/7/23.
#include <string>
#include <iostream>
#include <algorithm> // reverse, max 函数均位于该头文件中
#include <vector>

using namespace std;

int main(void) {
    string s;
    string rs;
    while (cin >> s) {
        rs = s; // 复制
        reverse(rs.begin(), rs.end()); // 逆置

        // 动态规划初始化
        int length = s.size();
        vector<vector<int>> lcs(length + 1, vector<int>(length + 1, 0));

        /* 思路解释
         * 两个字符串 BDCABA 和 ABCBDAB, 字符串 BCBA 和 BDAB 都是是它们的最长公共子序列
         * lcs[i][j] 表示 s1 长度为 i, s2 长度为 j 时的最大公共子串长度
         * 现在已知 lcs[i - 1][j] 即 s1 长度为 i - 1, s2 长度为 j 时的最大公共子串长度
         * 而且已知 lcs[i][j - 1] 即 s1 长度为 i, s2 长度为 j - 1 时的最大公共子串长度
         * 当 s1 与 s2 同时增加一个字符之后, 判断 lcs[i][j] 的最大公共子串长度
         * 动态方程, 如果 s1 和 s2 增加的字符是相同的, 则最大公共子串长度可以 + 1, 否则最大公共子串长度为 lcs[i-1][j] 或 lcs[i][j-1]
        */
        for (int i = 1; i <= length; i++) {
            for (int j = 1; j <= length; j++) {
                if (s[i - 1] == rs[j - 1]) {
                    lcs[i][j] = lcs[i - 1][j - 1] + 1;
                }
                else {
                    lcs[i][j] = max(lcs[i][j - 1], lcs[i - 1][j]);
                }
            }
        }

        cout << length - lcs[length][length] << endl;
    }
}