首页 > 其他 > 详细

最长回文子串与最长回文子序列

时间:2020-10-31 18:15:12      阅读:3      评论:0      收藏:0      [点我收藏+]

最长回文子串

  • 定义状态
    \(dp[i][j]\) 表示子串 \(s[i..j]\) 是否为回文子串,这里子串 \(s[i..j]\) 定义为左闭右闭区间,可以取到 \(s[i]\)\(s[j]\)

  • 状态转移方程
    \(dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]\)

  • 编码技巧
    本体是典型的二维dp.因为子串是连续的,短的子串会为通过递进的方式,从而可以判断长的子串。因此本体的遍历方式第一层for 循环控制遍历子串的长度,第二层for循环为子串的左边界,当然右边界根据左边界以及子串的长度可以很轻松得到

class Solution {
public:
    string longestPalindrome(string s) {
        string ans = "";    
        int n = s.size(); 
        vector<vector<bool>> dp(n , vector<bool> (n, false));
        for(int l = 0; l < n; l++){
            for(int i = 0; i + l < n; i++){
                int j = i + l;
                if (l == 0)
                    dp[i][j] = true;
                else if (l == 1)
                    dp[i][j] = s[i] == s[j];
                else 
                    dp[i][j] = ( (s[i] == s[j]) && dp[i+1][j-1] );
                
                if (dp[i][j] && l + 1 > ans.size())
                    ans = s.substr(i, l+1);
            }
        }
        return ans;
    }
};

最长回文子序列

这里我们一定要注意到,最长回文子序列与最长子串的区别,子序列相对子串可以是不连续的,也就是自序列是原本字符串中提取的一系列字符串,另外子序列不能改变原来子串的长度!!

  • 递推公式
    \(dp[i][j] = dp[i+1][j-1] + 2; s[i] == s[j]\)
    \(dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); s[i] != s[j]\)
  • 编码技巧
    这里因为子序列是不连续的,所以我们没法再像上面的解法,先使用一个for 循环 一下长度, 我们在这里直接遍历两个指针的所有情况!但是注意啊,根据动态规划方程我们可以得知 \([i,j]\) 是由\([i+1, j-1]\)递推而来的,也就是所\(i+1 -> i\), \(j-1->j\),所以\(i\)应该反着遍历,而\(j\)应该正着遍历。
class Solution {
public:
int longestPalindromeSubseq(string s) {
    int n = s.size();
    // dp 数组全部初始化为 0
    vector<vector<int>> dp(n, vector<int>(n, 0));
    // base case
    for (int i = 0; i < n; i++)
        dp[i][i] = 1;
    // 反着遍历保证正确的状态转移
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            // 状态转移方程
            if (s[i] == s[j])
                dp[i][j] = dp[i + 1][j - 1] + 2;
            else
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
    // 整个 s 的最长回文子串长度
    return dp[0][n - 1];
}
};
          

最长回文子串与最长回文子序列

原文:https://www.cnblogs.com/wsl-hitsz/p/13906784.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号