【每日一题】回文串移除方案

给定一个字符串 str，能否从字符串中移除部分（0个或多个）字符使其变为回文串，此处空串认为是回文串，求多少移除方案。（注意：相同字符的由于的移除，认为不同的移除方案）。

【例如】str = “XXY” 有 4 中移除方案

方案一：暴力规划

移除字符与保留字符效果是一样的。

可能性尝试：范围尝试模型。

f( i , j ) 定义：str[ i: j+1 ] 子串中包含回文个数。最终结果：f ( 0, len(str) - 1 )

可能性分类：

以上所有分类：互斥。最终的解是所有可能性的全集：求和。

要求 f (i,j) 解，必须先得到 f( i, j) 最近的子问题

f ( i, j-1 ) 是 str[ i: j ]子串中包含回文个数，不包含字符 str[j] ，所以以 j 结尾的可能性都不可能。

f ( i, j-1 ) = ③ + ④

同理：

f ( i+1, j ) = ② + ③

f ( i+1, j-1 ) = ③

现在缺少可能性 ①

可能性① 要求：以 i 开头且以 j 结尾。如果str[i] != str[j]，不可能出现可能性 ①

此时结果：f ( i, j ) = f ( i, j-1 ) + f ( i+1, j ) - f ( i+1, j-1 ) = （③ + ④）+ （ ② + ③）- ③ = ② + ③ + ④

如果str[i] == str[j]：不可能出现可能性 ③，③ = 0

f ( i, j ) = f ( i, j-1 ) + f ( i+1, j ) + 1 = ② + ④ + 1

1 是 str[i]str[j] 这个回文串

def min_remove(string):
    if not string: return 0
    return f(string, 0, len(string) - 1)


def f(string, i, j):
    if i == j: return 1
    if i + 1 == j: return 3 if string[i] == string[j] else 2

    res = f(string, i, j - 1) + f(string, i + 1, j)
    if string[i] == string[j]:
        res += 1
    else:
        res -= f(string, i + 1, j - 1)
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方案二：动态规划

def min_remove2(string):
    if not string: return 0
    n = len(string)
    dp = [[0] * n for _ in range(n)]
    dp[-1][-1] = 1
    for i in range(n - 1):
        dp[i][i] = 1
        dp[i][i + 1] = 3 if string[i] == string[i + 1] else 2

    for row in range(n - 3, -1, -1):
        for col in range(row + 2, n):
            dp[row][col] = dp[row][col - 1] + dp[row + 1][col]
            if string[row] == string[col]:
                dp[row][col] += 1
            else:
                dp[row][col] -= dp[row + 1][col - 1]

    return dp[0][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

方案三：动态规划–滚动数组

def min_remove3(string):
    if not string: return 0
    if len(string) == 1: return 1
    n = len(string)
    dp = [1] * n
    dp[-1] = 3 if string[-1] == string[-2] else 2

    for row in range(n - 3, -1, -1):
        tmp = 1
        dp[row + 1] = 3 if string[row + 1] == string[row] else 2
        for col in range(row + 2, n):
            new_value = dp[col - 1] + dp[col]
            if string[row] == string[col]:
                new_value += 1
            else:
                new_value -= tmp
            tmp = dp[col]
            dp[col] = new_value

    return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

对数器

import random

def generator_random_str(max_size):
    alphabet = [chr(i) for i in range(97, 105)]
    size = int(random.random() * max_size)
    return ''.join([random.sample(alphabet, 1)[0] for _ in range(size)])

def check():
    max_size = 10
    for i in range(500):
        stirng1 = generator_random_str(max_size)

        res1 = min_remove(stirng1)
        res2 = min_remove2(stirng1)
        res3 = min_remove3(stirng1)

        if res1 != res2 or res1 != res3:
            print("ERROR", stirng1, "res1=", res1, "res2=", res2, "res3=", res3)
    print("OVER")

check()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

总结：本题考察是范围尝试模型，难点在于可能性分类后，要组合出最终的答案。