具有不同相鄰字元的最長子序列

---

介紹

在本教程中，我們將實現一種方法來查詢具有不同相鄰字元的最長子序列。這裡，最長子序列是指包含具有不同相鄰字元的最大數量的字串字元的子序列。為了實現查詢最長子序列的方法，請考慮一個字串 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() 使用輸入字串返回最大長度或最長子序列。它遍歷輸入字串的字元以查詢其相鄰字元不同的最長子序列。它使用貪心演算法來找到最有效的輸出。

#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() 以查詢具有不同相鄰字元的最長子序列，方法是儲存非重複的相鄰字元。

#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++ 中實現具有不同相鄰字元的最長子序列的問題陳述。

動態規劃降低了問題的複雜性，並且不會多次重複相同的步驟。相反，它將任務劃分為塊。但它解決起來很複雜。

貪心演算法易於實現和理解，但它會增加問題的​​時間複雜度。