具有不同相邻字符的最长子序列

介绍

在本教程中，我们将实现一种方法来查找具有不同相邻字符的最长子序列。这里，最长子序列是指包含具有不同相邻字符的最大数量的字符串字符的子序列。为了实现查找最长子序列的方法，请考虑一个字符串 s，并进行迭代

我们使用两种方法来解决查找具有不同相邻字符的最长子序列的问题陈述。

  • 贪心算法

    它是解决数据结构问题最常用的算法之一。这种方法尝试所有可能的情况并选择最合适的情况。

  • 动态规划

    它是对贪心算法的一种改进且耗时更少的方法。动态规划将任务划分为块，并独立地解决每个块以找到最有效的解决方案。

演示 1

Input = String = "xyyx"
Output = The longest subsequence with different adjacent characters is xy

解释

在上面的输入字符串“xyyx”中，最长的可能子序列是“xy”，因为它的相邻字符不同。在最长子序列中，“x”的相邻字符是“y”，“y”的相邻字符是“x”。输出子序列中没有重复的相邻字符。

演示 2

Input = String = "xyzyy"
Output = The longest subsequence with different adjacent characters is xyz.

解释

在上面的输入字符串“xyzyy”中，最长的可能子序列是“xyzy”，具有不同的相邻字符。这里，“y”的相邻字符是“x”和“z”。“x”的相邻字符是“y”，“z”的相邻字符是“y”。

C++ 库函数

  • size() - 它是 C++ 标准库中一个预定义的库函数。它返回输入字符串的长度。

string_name.size();

  • back() - 此字符串类库函数在 <string> 头文件中定义。它返回字符串最后一个字符的引用。

string_name.back();

  • empty() - 它是 <string> 头文件中一个预定义的函数。它检查字符串的长度是否为 0，这意味着字符串是否为空。

string_name.empty();

  • memset() - 此库函数在 <cstring> 头文件中定义。它为某些值分配内存块。它接受 3 个参数：dest、ch 和 cnt。Des 是要复制的源，ch 是字符，cnt 是块的数量。

memset(dest, ch, cnt);

  • length() - 它是 <string> 头文件中定义的字符串类库函数。它以字节形式返回输入字符串的长度。字符串的长度是字符数。

string_name.length();

算法

  • 获取输入字符串。

  • 遍历输入字符串的每个字符。

  • 将第一个字符存储在一个字符串变量中，并将其与下一个字符进行比较。

  • 如果字符与前一个字符不同，则将其存储在一个字符串变量中，否则拒绝此字符。

  • 重复步骤 4 直到找到具有不同相邻字符的最长子序列。

  • 打印结果。

示例 1

在此 C++ 实现中，longestSubsequence() 使用输入字符串返回最大长度或最长子序列。它遍历输入字符串的字符以查找其相邻字符不同的最长子序列。它使用贪心算法来找到最有效的输出。

Open Compiler
#include <iostream>
#include <string>
using namespace std;

//finding the longest subsequence having different adjacent characters
string longestSubsequence(const string& input) {
   string subsequence;
   string result;

   //iterating each character of the input string
   for (char ch : input) {
      if (result.empty() || ch != result.back()) {
         result += ch;
      }  else {
         if (result.size() > subsequence.size()) {
            subsequence = result;
         }
         result = ch;
      }
   }

   if (result.size() > subsequence.size()){
      subsequence = result;
   }

   return subsequence;
}

//code controller
int main() {
   string input = "xyzyy";
   cout << "Input string: " << input << endl;

   string subsequence = longestSubsequence(input);
   cout << "Longest subsequence with different adjacent characters: " << subsequence << endl;

   return 0;
}

输出

Input string: xyzyy
Longest subsequence with different adjacent characters: xyz

示例 2

使用动态规划实现问题。初始化一个二维数组以存储结果值，并使用 memset() 初始化它。findLongestSubsequence() 函数递归调用 calculateSubsequence() 以查找具有不同相邻字符的最长子序列，方法是存储非重复的相邻字符。

Open Compiler
#include <bits/stdc++.h>
using namespace std;
int dp[100005][27];

string calculateSubsequence(int posl, int pre, const string& str) {   
   if (posl == str.length()) {
      return "";
   }
   if (dp[posl][pre] != -1) {
      return dp[posl][pre] == 1 ? string(1, str[posl]) : "";
   }
   if (str[posl] - 'a' + 1 != pre) {
      string newString = str[posl] + calculateSubsequence(posl + 1, str[posl] - 'a' + 1, str);
      string excludeString = calculateSubsequence(posl + 1, pre, str);
      if (newString.length() > excludeString.length()) { 
         return newString;
      } else {
         return excludeString;
      }
   } else  {
      return calculateSubsequence(posl + 1, pre, str);
   }
}
string findLongestSubsequence(const string& str){
   int l = str.length();
   memset(dp, -1, sizeof(dp));
   return calculateSubsequence(0, 0, str);
}
int main(){   
   string s = "xyzxx";
   string subsequence = findLongestSubsequence(s);
   cout << "Longest subsequence with different adjacent characters: " << subsequence << endl;
   return 0;
}

输出

Longest subsequence with different adjacent characters: xyzx

结论

我们已经完成了本教程，以查找具有不同相邻字符的最长子序列。相邻字符是字符的相邻字符。在本教程中，我们使用了 2 个演示来解释查找最长子序列的任务要求。使用了两种方法：贪心算法和动态规划，以在 C++ 中实现具有不同相邻字符的最长子序列的问题陈述。

动态规划降低了问题的复杂性，并且不会多次重复相同的步骤。相反，它将任务划分为块。但它解决起来很复杂。

贪心算法易于实现和理解，但它会增加问题的​​时间复杂度。

更新于： 2023 年 10 月 3 日

163 次查看

开启你的 职业生涯

通过完成课程获得认证

开始
广告