最长回文子序列问题

问题描述

回文是正序与逆序相同的非空字符串。例如，所有长度为1的字符串、civic、racecar、aibohphobia（害怕回文之意）都是回文。

设计高效算法，求给定输入字符串的最长回文子序列。例如，给定输入 character，算法应该返回 carac。算法的运行时间是怎么样的？

题解

本题出自《算法导论》第 15 章的思考题15-3。这道题可以使用暴力罗列的方法做，那么总共会有 $2^n$ 种情况，算法的复杂度也为 $O(2^n)$ ，其中 $n$ 为输入字符串的长度。

为了减小算法的复杂度，可以使用动态规划的方法解决。

给定任意一个输入串 $X = {x_1, x_2, x_3, x_4… x_n}$，定义其子串 $X_{i,j} = { x_i, x_{i+1}, x_{i+2}, …, x_j}$。设一个函数 $f(X_{i,j})$，其定义如下：

$$f(X_{i,j})= 1 , X_{i,j}是回文序列 $$
$$f(X_{i,j})= 0 , X_{i,j}不是回文序列$$

对于任意一个子串 $X_{i,j}$，分以下几种情况讨论：

$ x_i = x_j $，则此时 $X_{i,j}$是否是回文子序列，与 $x_i$和 $x_j$无关，可以将其从 $ X_{ij} $中去除。如果 $X_{i+1, j-1} $是一个回文序列，则 $X_{i, j}$ 也是一个回文序列；如果 $X_{i+1, j-1} $不是一个回文序列，则 $X_{i, j}$也不是一个回文序列。例如，给定一个序列 $ 1w1 $，其中 $w$是一段字符串序列。由于这个序列左右两端是相同的，因此当 $w$是一个回文序列时， $1w1$才是一个回文序列；反之亦然。所以，我们可以给出如下式子：
$$ f(X_{i,j}) = f(X_{i+1, j - 1}), x_i = x_j$$

$ x_i \neq x_j$，则此时由于 $X_{i, j}$两端的字符不同，其当然不是回文序列。同上，我们有：
$$ f(X_{i,j}) = 0, x_i \neq x_j$$

除此之外，我们还知道，一个只含有单个字符的字符串是回文序列；一个只有两个字符的字符串，即 $X_{i, i+1}$，如果有 $x_i = x_{i+1} $，则其也是回文序列。

综上，我们给出 $f(X_{i, j})$的完整递归式：
$ f(X_{i, j}) = 1 , i = j $
$f(X_{i, j}) = 1 , x_i = x_j, j = i + 1 $
$ f(X_{i, j}) =f(X_{i+1, j-1}) ,x_i = x_j $
$f(X_{i, j}) = 0 , x_i \neq x_j $

我们不妨使用一个 $ n \times n $的矩阵来储存 $f(X_{i, j})$的值。我们给出如下伪代码：

 LONGEST-PALINDROME-SUBSEQUENCE(S)
1   n = S.length
2   let p[1 ... n, 1 ... n] be a new table
3   for i = 1 to n
4       for j = 1 to n
5           if i == j
6               p[i][j] = 1
7           else
8               p[i][j] = 0
9   for i = 1 to n-1
10      for j = 1 to n-i
11          if i == 1
12              if S[j] == S[j+1]
13                  p[j][j+1] = 1
14          else if x[j] == x[j + i]
15              p[j][j+i] = p[j+1][j+i-1]
16          else
17              p[j][j+i] = 0
18
19  max_length = -1, left = 0, right = 0
20  for i = 1 to n
21      for j = 1 to n
22          if j - i > max_length
23              max_length = j - i
24              left = i, right = j
25  return S[left:right]

使用Python的实现如下：

import numpy as np 

def LPS(s):
    if len(s) <= 1:
        return s
    p = np.zeros((len(s), len(s)))
    for i in range(len(s)):
        p[i][i] = 1
    for i in range(1, len(s)):
        for j in range(len(s) - i):
            if i == 1:
                if s[j] == s[j+i]:
                    p[j][j+i] = 1
            else:
                if s[j] == s[j+i]:
                    p[j][j+i] = p[j+1][j+i-1]
                else:
                    p[j][j+i] = 0
    max_len = -1
    l, r = -1, -1
    for i in range(len(s)-1):
        for j in range(i, len(s)):
            if p[i][j] == 1 and j - i > max_len:
                l, r = i, j
                max_len = j - i
    return s[l:r+1]

显然，该算法的复杂度为 $ O(n^2) $，远比暴力求解的 $O(2^n)$要好。