数据结构
网络
关系数据库管理系统 (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 次浏览
广告