腾讯，构造回文

忘是亡心i 2022-03-30 04:42 347阅读 0赞

**题目描述**  
给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？  
输出需要删除的字符个数。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]

--------------------

## 算法思想 ##

思想就是找出s和s的翻转序列最长公共子序列的个数  
最长公共子序列算法LCS算法，写成动态规划的格式：  
![在这里插入图片描述][20190104201443671.png]  
也就是，如果xi和yj相等，那么最长公共子序列的长度就是c\[i-1\]\[j-1\]+1  
如果不相等，就是c\[i\]\[j-1\]和c\[i-1\]\[j\]的最大值

--------------------

## 通过代码 ##

需要使用python处理键盘的多行输入，否则后面的输入会输出空，程序是不能通过的。

import sys
    def LCS(s1, s2):
        m = len(s1)
        n = len(s2)
        c = [([0] * (n + 1)) for i in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i - 1] == s2[j - 1]:
                    c[i][j] = c[i - 1][j - 1] + 1
                else:
                    c[i][j] = max(c[i - 1][j], c[i][j - 1])
        return c[m][n]
    try:
        while True:
            s1 = sys.stdin.readline().strip()
            if s1 == '':
                break
            listS = list(s1)
            listS.reverse()
            s2 = ''.join(listS)
            length = len(s1)
            lcs = LCS(s1, s2)
            print(length - lcs)
    except:
        pass

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: /images/20220330/0a066a24bcd04bd499ed78ad170d9f24.png
[20190104201443671.png]: /images/20220330/59cc1dc84a6d46deaa2f4e415d47ff6b.png