[LeetCode] 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, and there exists one unique longest palindromic substring.

http://www.acmerblog.com/longest-palindromic-subsequence-5721.html

最直接的解决方法是：生成给定字符串的所有子序列，并找出最长的回文序列，这个方法的复杂度是指数级的。下面来分析怎么用动态规划解决。

1）最优子结构

假设 X[0 ... n-1] 是给定的序列，长度为n. 让 L(0,n-1) 表示序列 X[0 ... n-1] 的最长回文子序列的长度。

1. 如果X的最后一个元素和第一个元素是相同的，这时：L(0, n-1) = L(1, n-2) + 2 , 还以 “BBABCBCAB” 为例，第一个和最后一个相同，因此 L(1,n-2) 就表示蓝色的部分。

2. 如果不相同：L(0, n-1) = MAX ( L(1, n-1) , L(0, n-2) )。以”BABCBCA” 为例，L(1,n-1)即为去掉第一个元素的子序列，L(0, n-2)为去掉最后一个元素。

有了上面的公式，可以很容易的写出下面的递归程序：

#include<stdio.h>
#include<string.h>
int lps(char *seq, int i, int j)
{
   //一个元素即为1
   if (i == j)
     return 1;
   if(i > j) return 0; //因为只计算序列 seq[i ... j]

   // 如果首尾相同
   if (seq[i] == seq[j])
      return lps (seq, i+1, j-1) + 2;

   // 首尾不同
   return max( lps(seq, i, j-1), lps(seq, i+1, j) );
}

/* 测试 */
int main()
{
    char seq[] = "acmerandacm";
    int n = strlen(seq);
    printf ("The lnegth of the LPS is %d", lps(seq, 0, n-1));
    getchar();
    return 0;
}

重叠子问题

画出上面程序的递归树(部分)，已一个长度为6 的字符串为例：

             L(0, 5)
           /         
          /            
      L(1,5)          L(0,4)
     /                /    
    /                /      
L(2,5)    L(1,4)  L(1,4)  L(0,3)

可见有许多重复的计算，例如L(1,4)。该问题符合动态规划的两个主要性质: 重叠子问题 和 最优子结构 。

下面通过动态规划的方法解决，通过自下而上的方式打表，存储子问题的最优解。

int lpsDp(char * str,int n){
    int dp[n][n], tmp;
    memset(dp,0,sizeof(dp));
    for(int i=0; i<n; i++) dp[i][i] = 1;
    // i 表示 当前长度为 i+1的 子序列
    for(int i=1; i<n; i++){
        tmp = 0;
        //考虑所有连续的长度为i+1的子串. 该串为 str[j, j+i]
        for(int j=0; j+i<n; j++){
            //如果首尾相同
            if(str[j] == str[j+i]){
                tmp = dp[j+1][j+i-1] + 2;
            }else{
                tmp = max(dp[j+1][j+i],dp[j][j+i-1]);
            }
            dp[j][j+i] = tmp;
        }
    }
    //返回串 str[0][n-1] 的结果
    return dp[0][n-1];
}

方法一：动态规划

DP, and the state transfer:

f(i, j) = ture; if i == j
　　　　S[i] == S[j] ,if j = i + 1
　　　　S[i] == S[j] and f(i + 1, j - 1) ,if j > i + 1

class Solution {
    public:
        string longestPalindrome(string s)
        {
            size_t len = s.size();
            char f[len][len];
            size_t start = 0;
            size_t max = 0;

            memset(f,0,sizeof(f));

            for(int i = 0; i < len; i++)
            {
                for(int j = 0; j <= i; j++)
                {
                    if((j == i) || (i == (j+1) && s[i] == s[j])
                            || ((i > (j + 1)) && s[i] == s[j] && f[j+1][i-1]))
                    {
                        f[j][i] = 1;
                        //cout << "f["<<j<<"][" <<i<<"]
";

                        if((i - j +1) > max)
                        {
                            start = j;
                            max = i - j + 1;
                        //    cout << "start	" <<start <<endl;
                        //    cout << "max	" <<max<<endl;
                        }
                    }
                }
            }
            return s.substr(start, max);
        }
};

方法二：将原来的字符串reverse一下，为newStr，求原来的str和新的newStr的 longest common substr 即可，对于longest common substr的求法，参考我的下篇随笔。