C ++中最长的回文序列

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个字符串s，我们必须找到最长回文子序列的长度s。我们可以假设s的最大长度为1000。因此，如果输入类似“ bbbab”，则输出将为4。一种可能的回文子序列是“ bbbb”。

为了解决这个问题，我们将遵循以下步骤-

  • x：= s，然后反转x，n：= s的大小

  • 如果n为0，则返回0

  • 通过在s之前添加一个空格来更新s，并通过在x之前添加一个空格来更新x

  • ret：= 0

  • 使一个矩阵dp的大小为（n + 1）x（n + 1）

  • 对于我在1到n范围内

    • dp [i，j]：= dp [i，j – 1]，dp [i – 1，j]的最大值

    • 如果x [i] = s [j]，则dp [i，j]：= dp [i，j]的最大值和1 + dp [i – 1，j – 1]

    • 对于j在n到n范围内

    • 返回dp [n，n]

    让我们看下面的实现以更好地理解-

    示例

    #include <bits/stdc++.h>
    using namespace std;
    class Solution {
       public:
       int longestPalindromeSubseq(string s) {
          string x = s;
          reverse(x.begin(), x.end());
          int n = s.size();
          if(!n) return 0;
          s = " " + s;
          x = " " + x;
          int ret = 0;
          vector < vector <int> > dp(n + 1, vector <int>(n + 1));
          for(int i = 1; i <= n; i++){
             for(int j = 1; j <= n ; j++){
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                if(x[i] == s[j]) {
                   dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
                }
             }
          }
          return dp[n][n];
       }
    };
    main(){
       Solution ob;
       cout << (ob.longestPalindromeSubseq("bbbab"));
    }

    输入项

    "bbbab"

    输出结果

    4

    以上是 C ++中最长的回文序列 的全部内容， 来源链接： utcz.com/z/351559.html

    回到顶部