C++ 从给定数组中选择字符串并满足条件后的最大字符串长度

在这个问题中，我们需要通过将数组字符串追加到一个字符串中，找到最大的结果字符串的长度。这样，如果我们选择了一个长度为x的字符串，我们可以选择接下来的x/2个字符串。

我们可以使用递归函数、记忆化和动态规划方法来解决这个问题。

问题陈述-我们有一个名为str_array的字符串数组，其中包含N个字符串。我们需要将数组中给定的字符串添加到结果字符串中，并找到结果字符串的最大长度。在将字符串追加到结果字符串时，我们需要遵循以下规则：如果我们选择任何长度为x的字符串，那么我们不能选择数组中的接下来的x/2个字符串。

示例样例

输入

str_array[] = {"tutor", "po", "nt", "welco", "ghj"}

输出

10

解释 - 我们可以选择“tutor”和“welco”字符串。

输入

str_array[] = {"tu", "po", "nt", "wel", "ghj"}

输出

7

说明 - 我们可以选择“tu”、“nt”和“ghj”字符串。结果字符串的长度将为7。

输入

str_array[] = {"tutorialspoint", "po", "nt", "wel", "ghj"};

输出

14

解释 - 我们只能选择“tutorialspoint”字符串。

为了解决这个问题，我们需要对字符串进行2N次选择，并根据选择的最大长度选择最终答案。

方法1

在这个方法中，我们将创建一个递归函数来考虑字符串的所有选择，并根据所有选择选择最大长度。

算法

步骤1 - 首先，定义基本情况。如果数组长度小于start，返回0。

步骤2 - 现在，我们必须对当前字符串进行选择。第一种选择是包含字符串。如果我们包含字符串，将字符串大小添加到递归函数的返回值中。同时，改变start参数的值，因为我们无法选择下一个x/2的长度，其中x是字符串长度。

步骤3 - 如果我们不包含当前字符串，在增加start参数值1之后，进行递归函数调用。

步骤4 - 从sol1和sol2中选择最大值并返回。

示例

#include <bits/stdc++.h>
using namespace std;

int maxStringSize(string str_array[], int len, int start) {
   // Return 0 if start exceeds len
   if (start >= len)
      return 0;
   // If value is not calculated for start index
       // Add current string
      int sol1 = str_array[start].size() + maxStringSize(str_array, len, 
(start + str_array
[start].size() / 2) + 1);
      // Remove current string
      int sol2 = maxStringSize(str_array, len, start + 1);
      // Take max of both
      int maxSize = max(sol1, sol2);
   // return answer
   return maxSize;
}
int main() {
   string str_array[] = {"tutor", "po", "nt", "welco", "ghj"};
   int len = sizeof(str_array) / sizeof(str_array[0]);
   cout << "The maximum size of the resultant string according to given conditions is  - " << maxStringSize(str_array, len, 0);
   return 0;
}

输出

The maximum size of the resultant string according to given conditions is - 10

时间复杂度 - O(2^N)，因为我们在递归函数中为所有字符串做出选择。

空间复杂度 - O(1)，因为我们使用了常数空间。

方法2

这种方法将使用记忆化技术来解决问题。它将先前计算出的结果存储在列表中。因此，如果我们需要再次计算相同的操作，就可以从列表中取值。

算法

步骤1 - 定义长度与数组长度相等的 ‘dp’ 列表，并将其初始化为 -1。

步骤2 - 如果开始位置大于数组长度，则返回0。

步骤3 - 如果 dp[start] 为 -1，我们第一次计算该值。

步骤4 - 执行递归函数调用。在一个函数调用中，包含开始索引处的字符串；在另一个函数调用中，不包含开始索引处的字符串。

步骤5 - 将两个解决方案中的最大值存储在 dp[start] 中。

步骤6 - 返回 dp[start] 的值。

例子

#include <bits/stdc++.h>
using namespace std;

int maxStringSize(string str_array[], int len, int start, vector<int> 
&dp) {
   // Return 0 if start exceeds len
   if (start >= len)
      return 0;
   // If value is not calculated for start index
   if (dp[start] == -1) {
      // Add current string
      int sol1 = str_array[start].size() + maxStringSize(str_array, len, 
(start + str_array[start].size() / 2) + 1, dp);
      // Remove current string
      int sol2 = maxStringSize(str_array, len, start + 1, dp);
      // Take max of both
      dp[start] = max(sol1, sol2);
   }
   // return answer
   return dp[start];
}
int main() {
   string str_array[] = {"tutor", "po", "nt", "welco", "ghj"};
   int len = sizeof(str_array) / sizeof(str_array[0]);
   vector<int> dp(len, -1);
   cout << "The maximum size of the resultant string according to given conditions is " << maxStringSize(str_array, len, 0, dp);
   return 0;
}

输出

The maximum size of the resultant string according to given conditions is 10

时间复杂度 – O(N*M)，其中N是数组的长度，M是字符串的最大长度。

空间复杂度 – O(N)，因为我们为每个起始索引存储结果值。

方法3

在这种方法中，我们将使用动态规划的表格方法来解决问题。它通过迭代填充列表并根据先前状态决定答案。

算法

步骤1 - 定义’matrix’列表。

步骤2 - 将matrix的最后一个元素初始化为0。

步骤3 - 从最后一个索引开始遍历数组。

步骤4 - 将sol1变量初始化为字符串大小。如果p + str_array[p].size() / 2 + 1小于或等于数组长度，则从matrix的(p + str_array[p].size() / 2 + 1)索引处将值添加到sol1。

步骤5 - 定义’sol2’并将其初始化为matrix[p+1]。

步骤6 - 在matrix[p]中存储sol1和sol2的最大值。

步骤7 - 返回matrix[0]的值。

例子

#include <bits/stdc++.h>
using namespace std;

int maxStringSize(string str_array[], int len) {
   // List to store results
   vector<int> matrix(len + 1);
   matrix[len] = 0; // Initialization
   // Traverse the string
   for (int p = len - 1; p >= 0; p--) {
      // Include string at pth index
      int sol1 = str_array[p].size();
      if (p + str_array[p].size() / 2 + 1 <= len) {
         sol1 += matrix[p + str_array[p].size() / 2 + 1];
      }
      // Don't include string at pth index
      int sol2 = matrix[p + 1];
      // Answer for last p strings
      matrix[p] = max(sol1, sol2);
   }
   // Return final result
   return matrix[0];
}
int main() {
   string str_array[] = {"tutor", "po", "nt", "welco", "ghj"};
   int len = sizeof(str_array) / sizeof(str_array[0]);
   cout << "The maximum size of the resultant string according to given conditions is " << maxStringSize(str_array, len);
   return 0;
}

输出

The maximum size of the resultant string according to given conditions is 10

时间复杂度 - 遍历字符串，时间复杂度为O(N)。

空间复杂度 - 使用列表存储前面的结果，空间复杂度为O(N)。

从上述三种方法来看，表格技术在时间复杂度方面最好。记忆化技术是递归方法的优化版本，因为我们使用了先前计算出的结果。