2017-05-12

算法设计与分析[0012] Dynamic Programming(IV)（Longest Palindromic Subsequence）

　所谓 回文（palindrome），指的是正读和反读都是一样的。而 字符子串 和 字符子序列 的区别，在前面算法设计与分析[0011] Dynamic Programming(III)（Longest Common Subsequence）中也有提到过，字符字串指的是字符串中连续的n个字符，而字符子序列指的是字符串中不一定连续但先后顺序与原字符串一致的n个字符。

最长回文字符串

5. Longest Palindromic Substring 题目描述如下：

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
> Example:
　Input: “babad”
　Output: “bab”
Note: “aba” is also a valid answer.
> Example:
　Input: “cbbd”
　Output: “bb”

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        /*
         * isPalindrome[i][j]: str[i...j] is a palindrome substring
         * n ≤ 1000
         */
        bool isPalindrome[n][n] = {false};
        // <1> palindrome substring with length 2, a single char is a palindrome substring
        for(int strIdx=0; strIdx<n; strIdx++) {
            isPalindrome[strIdx][strIdx] = true;
        }
        // longest palindrome substring s[longestStartIdx,longestStartIdx+longestLen-1] with length:longestLen
        int longestStartIdx=0;
        int longestLen = 1;
        
        // <2> palindrome substring with length 2
        for(int strIdx=0; strIdx<n-1; strIdx++) {
            if(s[strIdx+1] == s[strIdx]) {
                isPalindrome[strIdx][strIdx+1] = true;
                longestLen = 2;
                longestStartIdx = strIdx;
            }
        }
        // <3> palindrome substring with length:len
        for(int len=3; len<=n; len++) {
            for(int strIdx=0; strIdx<=n-len; strIdx++) {
                int endIdx = strIdx+len-1;
                if(s[endIdx] == s[strIdx] && isPalindrome[strIdx+1][endIdx-1]) {
                    isPalindrome[strIdx][endIdx] = true;
                    if(len > longestLen) {
                        longestLen = len;
                        longestStartIdx = strIdx;
                    }
                }
            }
        }
        
        return s.substr(longestStartIdx, longestLen);
    }
};

代码实现细节
- isPalindrome[i][j]：字符子串 $s[i][j]$ 是否是回文子串？
- 动态规划过程：依次遍历长度为 $1, 2, …, len, …, n(本题: \leq 1000)$ 的所有子串，判断子串 $s[strIdx, strIdx+len-1], strIdx \in [0, n-len]$ 是否为回文子串
  - 动态规划初始化①：长度为 1 的子串均为回文子串，即 $\qquad isPalindrome[i][i]=true, i \in [0, n)$
  - 动态规划初始化②：长度为 2 的子串，相邻两个字符相同的子串也为回文子串，即 $\begin{cases} if(s[i] == s[i+1]): \cr \quad isPalindrome[i][i+1]=true \cr else: \cr \quad isPalindrome[i][i+1]=false \end{cases} i \in [0, n-1)$
  - 动态规划填表过程 $isPalindrome[i][j]$：$\begin{cases} for 　 len=3, …, n: \cr \quad for 　 i=0, 1, …, n-len: \cr \qquad j=i+len-1 \cr \qquad if(s[i] == s[j] \&\& isPalindrome[i+1][j-1]): \cr \qquad \quad isPalindrome[i][j]=true \cr \qquad else: \cr \qquad \quad isPalindrome[i][j]=false \end{cases}$
- 在动态规划过程，通过变量 longestLen记录在动态规划过程中发现的最长回文子串长度及该子串在原始子串中的起始下标 longestStartIdx。
提取最长回文子串
- 最终得到最长回文子串：$\qquad s[longestStartIdx…longestStartIdx+longestLen-1] $

最长回文子序列

　对于任意字符子串，如果头尾字符相同：①由于子字符串必须是连续的，只有在该字符子串除去头尾字符后剩下的部分是回文的，该子字符串才是回文子串；②子序列，因为可以不连续，要求更宽松了，这种情况下，该子字符串存在一个长度至少为2的回文子序列，至于最长子序列，还要加上去掉首尾字符的字符串的最长子序列；
　如果首尾字符不同：①该子字符串一定不是回文子串；②对于最长回文子序列，为了尽可能增加长度（也许第二个字符正好与末尾字符相同/也许倒数第二个字符正好与首字符相同），最长回文子序列在去掉头的子字符串的最长回文子序列和去掉尾的子字符串的最长回文子序列中产生，为长度较大者。

[516. Longest Palindromic Subsequence] 解题思路
　基于上述思路，很容易想到如下的递归实现，不过由于递归中出现的多余计算、频繁的函数调用，在 leetcode 上提交会有：Time Limit Exceeded 超时错误。

递归实现

#define max(a,b) (a>b?a:b)
 
int lps(char* str, int fromIdx, int toIdx) {
    if(fromIdx==toIdx) {
        return 1;
    }
    if(str[fromIdx] == str[toIdx]) {
        if(toIdx-fromIdx==1) {
            return 2;
        }
        return lps(str, fromIdx+1, toIdx-1) + 2;
    }
    return max(lps(str, fromIdx+1, toIdx), lps(str, fromIdx, toIdx-1));
}
 
int longestPalindromeSubseq(char* s) {
    int n = strlen(s);
    return lps(s, 0, n-1);
}

　基于上述思路的动态规划实现，定义的子问题与最长回文子串有明显出入。
　①子问题：设字符串为 s，长度为 n，$dp[fromIdx][toIdx]$：子字符串 $s(fromIdx…toIdx)$ 中的最长回文子序列长度。
　②与最长回文子串类似，依次遍历长度为 $1, 2, …, len, …, n(本题: \leq 1000)$ 的所有子串，计算 $s(fromIdx…fromIdx+len-1)$ 中的最长回文子序列长度 $dp[fromIdx][fromIdx+len-1]$
　　状态初始条件（1）：长度为 1 的子串均为回文子序列，即 $\qquad \qquad dp[i][i]=1, i \in [0, n)$
　　状态初始条件（2）：长度为 2 的子串，相邻两个字符相同的子串也为回文子序列，即 $\begin{cases} if(s[i] == s[i+1]): \cr \quad dp[i][i+1]=2 \cr else: \cr \quad dp[i][i+1]=0 \end{cases} i \in [0, n-1)$
　　注：代码实现中将状态初始条件（2）这一过程附带在下一步填表过程中。
　　状态转移方程（填表过程）：$\qquad \qquad \begin{cases} for 　 len=3, …, n: \cr \quad for 　 i=0, 1, …, n-len: \cr \qquad j=i+len-1 \cr \qquad if(s[i] == s[j]): \cr \qquad \quad dp[i][j]=dp[i+1][j-1]+2 \cr \qquad else: \cr \qquad \quad dp[i][j]=max(dp[i+1][j], dp[i][j-1]) \end{cases}$

动态规划实现

#define max(a,b) (a>b?a:b)
 
int longestPalindromeSubseq(char* s) {
    int n = strlen(s);
    // dp[fromIdx][toIdx]: s(fromIdx,toIdx) is palindrome of length dp[fromIdx][toIdx]
    int dp[n][n];
    
    // strings of length 1 are palindrome of length 1
    for(int idx=0; idx<n; idx++) {
        dp[idx][idx] = 1;
    }
    
    for(int len=2; len<=n; len++) {
        for(int fromIdx=0; fromIdx<=n-len; fromIdx++) {
            int toIdx = fromIdx + len - 1;
            if(s[fromIdx] == s[toIdx]) {
                if(len==2) {
                    dp[fromIdx][toIdx] = 2;
                }
                else {
                    // s(fromIdx+1,toIdx-1) have smaller length:len-2
                    dp[fromIdx][toIdx]= dp[fromIdx+1][toIdx-1] + 2;
                }
            }
            else {
                // s(fromIdx+1,toIdx) & s(fromIdx,toIdx-1) have smaller length:len-1 
                dp[fromIdx][toIdx] = max(dp[fromIdx+1][toIdx], dp[fromIdx][toIdx-1]);
            }
        }
    }
    return dp[0][n-1];
}

提取最长回文子序列

利用动态规划过程的中间结果 dp[i][j]，使用与 提取最长公共子序列 一样的方法，能够提取出最长回文子序列。
在序列 s 中分别从头下标 fromIdx: 0 和尾下标 toIdx: n-1 向中间挪动，找出 dp[i][j] 个字符，即为提取的最长回文子序列。
如何在序列中向中间挪动呢？
- s[fromIdx]==s[toIdx]，当前字符在最长回文子序列中，头尾下标同时向中间挪：fromIdx++ & toIdx--。
- s[fromIdx]!=s[toIdx]，当前字符不相同
  - dp[fromIdx][toIdx-1] 大，说明 s[fromIdx] 可能是最长回文子序列的下一个字符，需要挪动尾下标：toIdx--；
  - 反之dp[fromIdx+1][toIdx] 大，则需要挪动头下标：fromIdx++。
挪动的边界条件：while(fromIdx≤toIdx)
- 出现 fromIdx==toIdx 后退出循环：最长回文子序列长度为奇数（如：”bab”），选择夹在原序列中最后一个相同字符间的任一字符作为唯一一个不成对字符。
- 直接因为 fromIdx<toIdx) 退出循环：最长回文子序列长度为偶数（如：”bb”），原序列中最后一个相同字符间不存在其它字符。

具体的代码实现如下：

string LPS;
fromIdx = 0;
toIdx = n-1;
while(fromIdx<=toIdx) {
    if(s[fromIdx] == s[toIdx]) {
        LPS += s[fromIdx];
        fromIdx++;
        toIdx--;
    }
    else {
        if(dp[fromIdx][toIdx-1] < dp[fromIdx+1][toIdx]) {
            fromIdx++;
        }
        else {
            toIdx--;
        }
    }
}

本文标题:算法设计与分析[0012] Dynamic Programming(IV)（Longest Palindromic Subsequence）

文章作者:Gary

发布时间:2017-05-12, 14:00:22

最后更新:2020-03-28, 12:37:22

原始链接:http://durant35.github.io/2017/05/12/Algorithms_LongestPalindromicSubsequence/