每天一道编程题——构造回文

Code

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

输入描述:
输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.
输出描述:
对于每组数据，输出一个整数，代表最少需要删除的字符个数。

输入例子:
abcda
google
输出例子:
2
2

其实就是一个最长公用子序列（LCS）问题。
先看看LCS的算法吧
（关于装饰器memo，详情请看记忆体化的装饰器）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
'''
递归版
'''
def rec_lcs(a, b):
    '''
    思路：从字符串的末尾开始，逐个匹配，不符合的砍掉。
    '''
    @memo
    def L(i, j):
        if min(i, j) < 0: return 0  # 越界
        if a[i] == b[j]: return 1 + L(i - 1, j - 1)  # match得到的,左右各-1，结果+1，继续递归
        return max(L(i - 1, j), L(i, j - 1))  # 不符合的砍掉。砍掉左边或右边
    return L(len(a) - 1, len(b) - 1)
print rec_lcs('spock', 'asoka')
# 3

运行过程如图所示




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
'''
迭代版
'''
def lcs(a, b):
    '''
    cur[i-1]对应递归版本的L(i-1,j)
    pre[i],pre[i-1]对应递归版本的L(i,j-1)与L(i-1,j-1)
    '''
    n, m = len(a), len(b)
    pre, cur = [0] * (n + 1), [0] * (n + 1)
    for j in range(1, m + 1):
        pre, cur = cur, pre
        for i in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                cur[i] = pre[i - 1] + 1
            else:
                cur[i] = max(pre[i], cur[i - 1])
    return cur[n]

运行过程如图所示



原题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def lcs(a, b):
    '''
    cur[i-1]对应递归版本的L(i-1,j)
    pre[i],pre[i-1]对应递归版本的L(i,j-1)与L(i-1,j-1)
    '''
    n, m = len(a), len(b)
    pre, cur = [0] * (n + 1), [0] * (n + 1)
    for j in range(1, m + 1):
        pre, cur = cur, pre
        for i in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                cur[i] = pre[i - 1] + 1
            else:
                cur[i] = max(pre[i], cur[i - 1])
    return cur[n]
if __name__=='__main__':
    while True:
        try:
            a=raw_input()
            A = [i for i in a.strip()]
            print len(A)-lcs(A,list(reversed(A)))
        except:
            break

来自腾讯2017暑期实习生编程题

本文标题:每天一道编程题——构造回文

文章作者:Vincent Zhong

发布时间:2016-09-12, 12:44:44

最后更新:2019-07-07, 13:13:09

原始链接:https://wax8280.github.io/2016/09/12/每天一道编程题——构造回文/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
|