数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究从给定数组中根据给定条件选择字符串后，字符串的最大长度
在这个问题中，我们需要找到通过将数组字符串附加到结果字符串中获得的结果字符串的最大长度，前提是如果我们选择长度为 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 - 首先，定义基本情况。如果数组长度小于开始位置，则返回 0。
步骤 2 - 现在，我们必须对当前字符串做出选择。第一个选项是包含该字符串。如果我们包含该字符串，则将字符串大小添加到递归函数返回的值中。此外，更改开始参数值，因为我们不能选择接下来的 x/2 长度，其中 x 是字符串长度。
步骤 3 - 如果我们不包含当前字符串，则在将开始参数值加 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 - 将矩阵的最后一个元素初始化为 0。
步骤 3 - 从最后一个索引开始遍历数组。
步骤 4 - 将 sol1 变量初始化为字符串大小。如果 p + str_array[p].size() / 2 + 1 小于或等于数组长度，则从矩阵的 (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)，因为我们使用列表来存储先前结果。
从以上三种方法来看，表格化技术在时间复杂度方面是最好的。记忆化技术是递归方法的优化版本，因为我们使用了先前计算的结果。
164 次浏览
