检查是否存在 2 * K + 1 个非空字符串，它们的连接构成给定的字符串
在这个问题中，我们给出了一个字符串，我们需要将字符串分成 k + 1 个子字符串，使得 k + 1 个子字符串与其反向连接可以得到原始字符串。
观察可以解决问题。如果字符串的前 k 个字符和后 k 个字符相同，则可以说可以根据给定的条件创建一个 k + 1 个字符串。
问题陈述– 我们给出了一个长度为 N 的字符串，其中包含小写字母和正整数 K。我们需要确定是否可以找到总共 k + 1 个字符串，使得 A1、A2、A3、…、Ak、A(k + 1) 字符串的连接和它们的反转(即 AK、A(k-1)、…、A3、A2、A1)是原始字符串 s。
示例
输入 – str = "tutorialsotut"; k = 4
输出– 是
解释– 我们可以创建总共 5 (4 + 1) 个字符串，分别是 't'、'u'、't'、'o' 和 'rials'，当我们根据给定的条件将它们连接起来时，我们可以得到原始字符串。
输入– str = "ststs", k = 1
输出– 是
解释– 我们可以创建 's' 和 'tst' 共 2 个字符串。
输入– str = "spres", k = 3
输出– 否
解释– 我们无法创建总共 4 个字符串，以便它能够遵循问题陈述中给出的条件。
方法 1
在这种方法中，我们将使用 for 循环将字符串的前 k 个字符与后 k 个字符进行比较。如果字符串的前 K 个字符与后 k 个字符相等，则可以说可以创建 K + 1 个字符串，因此当我们按正序和逆序合并它们时，我们可以得到原始字符串。
算法
将字符串的长度存储在"len"变量中。
如果 2*k + 1 大于字符串长度，则返回 false，因为不可能通过按正序和逆序合并 k + 1 个字符串来获取原始字符串。
使用 for 循环遍历前 k 个和后 k 个字符。
在循环中，比较 str[i] 和 str[len - i - 1] 个字符。如果不相同，则返回 false。
如果 for 循环完成所有迭代而不执行 return 语句，则返回 true。
示例
#include <bits/stdc++.h>
using namespace std;
// 函数检查我们是否可以根据给定的条件通过连接字符串来生成 k+1 个子字符串以获取原始字符串。
bool findStrings(string str, int k) {
// 获取字符串的长度
int len = str.size();
// 如果字符串的长度小于 2*k+1，则返回 false
if (2 * k + 1 > len) {
return false;
}
// 遍历字符串，检查前 k 个字符是否等于后 k 个字符的反转
for (int i = 0; i < k; i++) {
if (str[i] != str[len - i - 1]) {
return false;
}
}
// 如果前 k 个字符等于后 k 个字符，则返回 true
return true;
}
int main() {
string str = "tutorialsotut";
int K = 4;
if (findStrings(str, K)) {
cout << "Yes, we can make k+1 substrings according to the given conditions.";
} else {
cout << "No, we can't make k+1 substrings according to the given conditions.";
}
return 0;
}
输出
Yes, we can make k+1 substrings according to the given conditions.
时间复杂度 – O(K)，因为我们遍历字符串的前 K 个字符。
空间复杂度 – O(1)，因为我们使用常量空间。
方法 2
此方法使用 substr() 方法从原始字符串中获取子字符串。此外，我们将使用 reverse() 方法来反转子字符串。
在这里，我们将比较前 k 个字符和后 k 个字符的反转。如果它们相等，我们可以说可以创建 k + 1 个子字符串，这样合并后就可以得到实际的字符串。
算法
如果给定字符串的长度大于 2*k + 1，则返回 false。
使用 substr() 方法从 [0, k] 索引获取子字符串，并将其存储到"first"变量中。
再次使用 substr() 方法，从 [len - k, len] 索引获取子字符串，并将其存储到"last"变量中。
使用 reverse() 方法反转最后一个字符串。
返回 first == last 的布尔值。
示例
#include <bits/stdc++.h>
using namespace std;
// 函数检查是否可以生成 k+1 个子字符串，以便我们可以根据给定的条件连接字符串来获取原始字符串。
bool findStrings(string str, int k) {
// 获取字符串的长度
int len = str.size();
// 如果字符串的长度小于 2*k+1，则返回 false
if (2 * k + 1 > len) {
return false;
}
// 获取前 k 个字符
string first = str.substr(0, k);
// 获取后 k 个字符
string last = str.substr(len - k, k);
// 反转字符串
reverse(last.begin(), last.end());
// 如果两个字符串相等，则返回 true。否则，返回 false
return (first == last);
}
int main() {
string str = "ststs";
int K = 1;
if (findStrings(str, K)) {
cout << "Yes, we can make k+1 substrings according to the given conditions.";
} else {
cout << "No, we can't make k+1 substrings according to the given conditions.";
}
return 0;
}
输出
Yes, we can make k+1 substrings according to the given conditions.
时间复杂度 – O(K)，因为我们得到了子字符串。
空间复杂度 – O(K)，因为我们将长度为 K 的子字符串存储在"first"和"last"变量中。
我们学习了两种不同的解决问题的方法。第一种方法比第二种方法更优化，因为它的空间复杂度更低，时间复杂度相同。
