C++ 检查是否存在2 * K + 1个非空字符串，其连接形成给定的字符串

在这个问题中，我们给定了一个字符串，我们需要将字符串分成k + 1个子字符串，使得k + 1个子字符串与它们的反转的连接可以给我们原始字符串。

观察可以解决这个问题。如果字符串的前k个字符和后k个字符相同，我们可以说根据给定的条件可以创建一个k + 1个字符串。

问题陈述 - 我们给出了一个长度为N的字符串，其中包含小写字母字符和正整数K。我们需要找出是否可以找到总共k + 1个字符串，使得字符串s的连接A1，A2，A3，…，Ak，A(k + 1)字符串和它们的反转，即AK，A(k-1)，…，A3，A2，A1是原始字符串。

示例

输入 - 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个字符。

• 在循环中，比较str[i]和str[len – i – 1]字符。如果它们不相同，则返回false。

• 如果for循环在不执行return语句的情况下完成所有迭代，则返回true。

示例

#include <bits/stdc++.h>
using namespace std;
// function to check if we can make k+1 substrings to get the original string by concatenating strings according to the given conditions.
bool findStrings(string str, int k) {
   // get the length of the string
   int len = str.size();
   // If the length of the string is less than 2*k+1, return false
   if (2 * k + 1 > len) {
      return false;
   }
   // traverse the string to check whether the first k characters are equal to the reverse of the last k characters or not
   for (int i = 0; i < k; i++) {
      if (str[i] != str[len - i - 1]) {
          return false;
      }
   }
   // Return true if the first k characters are equal to the last k characters
   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;
// function to check if we can make k+1 substrings so that we can get the original string by concatenating strings according to the given conditions.
bool findStrings(string str, int k) {
   // get the length of the string
   int len = str.size();
   // If the length of the string is less than 2*k+1, return false
   if (2 * k + 1 > len) {
      return false;
   }
   // Get the first k characters
   string first = str.substr(0, k);
   // Get the last k characters
   string last = str.substr(len - k, k);
   // Reverse the string
   reverse(last.begin(), last.end());
   // Return true if both the strings are equal. Otherwise, return 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”变量中。

我们学习了两种不同的解决问题的方法。第一种方法比第二种方法更优化，因为它具有较低的空间复杂度和相同的时间复杂度。