資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學長度 k (k ≤ 3) 的迴文子序列個數
迴文是指一系列字母、數字或字元，其起始點和結束點相同。此外，從左到右讀和從右到左讀都是一樣的。
字串的子序列是一個新的字串，它是透過從原始字串中移除一些字元而建立的，而不會改變剩餘字元的相對順序。假設你有一個長度為N的字串。
你想從字串中找到長度為K的迴文子序列。請注意，K的值可以小於或等於3。在本文中，我們將使用 C++ 查詢這些子序列的個數。
輸入輸出場景
給定字串和K。輸出是該字串中長度為K的迴文子序列的個數。
Input: str = "aabaabb", K = 2 Output: 9 Input: str = "xxyyyxxzzy", K = 3 Output: 32
這裡，如果str = "aabaabb" 且 K = 2，我們有 9 個可能的子序列。它們是 aa, aa, aa, aa, aa, aa, bb, bb, bb。
如果 K = 1，結果將等於字串的長度。如果 K = 2，
使用遞迴
我們將使用遞迴從給定的字串中查詢長度為K的所有可能的子序列。首先，我們將建立一個布林函式來檢查字串是否為迴文。接下來，我們建立一個函式palindromicSubsequences來查詢可能的總數。
在這個函式中，我們使用遞迴來查詢字串中長度為K的所有可能的組合。然後，我們使用布林函式檢查新字串是否為迴文。如果條件為真，則計數變數增加一。
示例
#include <iostream>
#include <string>
using namespace std;
bool palindrome(const string& str) {
int start = 0, end = str.length() - 1;
while (start < end) {
if (str[start] != str[end]) {
return false;
}
start++;
end--;
}
return true;
}
int palindromicSubsequences(string str, int K, int begin, string sub, int
&count) {
for (int i = begin; i < str.length(); i++) {
sub += str[i];
palindromicSubsequences(str, K, i + 1, sub, count);
sub.pop_back();
}
if (sub.length() == K) {
if (palindrome(sub)) {
count++;
}
}
return count;
}
int main() {
string str = "xxyyyxxzzy";
int K = 3;
int count = 0;
int result = palindromicSubsequences(str, K, 0, "", count);
cout << "Number of palindromic subsequences of length " << K << " in the string " << str << ": " << result << endl;
return 0;
}
輸出
Number of palindromic subsequences of length 3 in the string xxyyyxxzzy: 32
使用陣列
我們將首先計算子序列的左右字元，以查詢有關字元頻率的資訊。接下來，我們遍歷字串的所有元素，並檢查子序列的左右字元是否為迴文。
示例
#include <iostream>
#define MAX 100
using namespace std;
const int max_value = 52;
void palindrome(string str, int N, int left[][MAX], int right[][MAX]) {
for (int i = 0; i < max_value; i++) {
for (int j = 0; j < N; j++) {
left[i][j] = 0;
right[i][j] = 0;
}
}
left[str[0] - 'x'][0] = 1;
for (int i = 1; i < N; i++) {
for (int j = 0; j < max_value; j++) {
left[j][i] += left[j][i - 1];
if (str[i] - 'x' == j) {
left[j][i]++;
}
}
}
right[str[N - 1] - 'x'][N - 1] = 1;
for (int i = N - 2; i >= 0; i--) {
for (int j = 0; j < max_value; j++) {
right[j][i] += right[j][i + 1];
if (str[i] - 'x' == j) {
right[j][i]++;
}
}
}
}
int palindromicSubsequences(int K, int N, int left[][MAX], int right[][MAX]) {
int count = 0;
if (K == 1) {
for (int i = 0; i < max_value; i++)
count += left[i][N - 1];
return count;
}
if (K == 2) {
count = 0;
for (int i = 0; i < max_value; i++) {
count += (left[i][N - 1] * (left[i][N - 1] - 1)) / 2;
}
return count;
}
for (int i = 1; i < N - 1; i++) {
for (int j = 0; j < max_value; j++) {
count += left[j][i - 1] * right[j][i + 1];
}
}
return count;
}
int main() {
string str = "xxyyyxxzzy";
int N = str.length();
int K = 3;
int left[max_value][MAX] = {
0
}, right[max_value][MAX] = {
0
};
palindrome(str, N, left, right);
int result = palindromicSubsequences(K, N, left, right);
cout << "Number of palindromic subsequences of length " << K << " in the string " << str << ": " << result << endl;
return 0;
}
輸出
Number of palindromic subsequences of length 3 in the string xxyyyxxzzy: 32
結論
我們討論了查詢字串中迴文子序列個數的不同方法。第一種方法是使用遞迴和排列的簡單方法。第二種方法使用陣列中的資料預計算來提高程式碼效率。
更新於：2024年1月5日
284 次瀏覽
廣告