通过增加给定长度的前缀来查找最终字符串
在这个问题中，我们需要增加数组中给定大小的多个前缀的每个字符。解决问题的简单方法是取数组中给定大小的每个前缀，并将前缀的每个字符增加 1。
最好的方法是使用给定的数组创建前缀数组，并在一次迭代中更新每个字符串字符。
问题陈述 - 我们给出了一个长度为 N 的字符串 alpha。此外，我们给出了一个包含正整数的前缀数组。prefixes[i] 表示从字符串中取出长度 prefixes[i] 的前缀，并将前缀的每个字符增加 1。还给出了循环增加字符。因此，'z' 变成 'a'。
示例
输入
alpha = "abcd"; prefixes[] = { 1, 1, 3 };
输出
'dcdd'
说明
由于 arr[0] 为 1，因此取长度为 1 的前缀，并增加每个前缀字符。结果字符串将为 'bbcd'。
对于第二个操作，取长度为 1 的前缀，并增加每个字符。结果字符串为'cbcd'。
在最后一个操作中，我们需要取长度为 3 的前缀，结果字符串为'dcdd'。
输入
alpha = "aabc"; prefixes[] = { 1, 2, 3, 4, 4, 3 };
输出
'gffe'
解释
在增加给定大小的每个前缀的每个字符后，结果字符串为'gffe'。
输入
alpha = "xyz"; prefixes[] = { 3, 2, 1 };
输出
'aaa'
解释
增加前 3 个字符后，字符串变为'yza'。
增加前 2 个字符后，字符串变为'zaa'。
增加前 1 个字符后，字符串变为'aaa'。
方法 1
在此方法中，我们将遍历数组并获取长度为 prefixes[i] 的字符串前缀。之后，我们将遍历前缀字符串并将每个字符加 1。
算法
步骤 1 - 使用 for 循环遍历数组前缀。
步骤 2 - 从索引 0 遍历字符串到前缀 [p]。
步骤 3 - 如果字符串中索引处的字符为"z"，则将字符更新为"a"。否则，将字符加 1。
步骤 4 - 当所有循环迭代完成后，返回 alpha 字符串。
示例
#include <bits/stdc++.h>
using namespace std;
string getFinalString(string alpha, int pref_array[], int pref_len) {
// 遍历前缀数组
for (int p = 0; p < pref_len; p++) {
// 循环增加 pref_array[p] 元素
for (int q = 0; q < pref_array[p]; q++) {
// 如果当前字符是 'z'
if (alpha[q] == 'z') {
alpha[q] = 'a';
} else {
// 将字符增加 1
alpha[q] += 1;
}
}
}
return alpha;
}
int main() {
string alpha = "abcd";
int prefixes[] = { 1, 1, 3 };
int pref_len = sizeof(prefixes) / sizeof(prefixes[0]);
cout << "The final string is " << getFinalString(alpha, prefixes, pref_len) << endl;
return 0;
}
输出
The final string is dcdd
时间复杂度 – O(N*M)，其中 N 是字符串长度，M 是数组长度。
空间复杂度 – O(1)，因为我们更新了 alpha 字符串。
方法 2
在这种方法中，我们将创建一个前缀数组并在一次迭代中递增字符串的所有字符。
算法
步骤 1 - 定义一个名为"arr"的数组，其长度等于前缀数组长度 + 1，并用 0 初始化所有元素。
步骤 2 - 开始遍历前缀数组并将 arr[pref_array[p]] 减少 1。此外，在每次迭代中增加 arr[0]。
步骤 3 - 现在，遍历'arr' 数组从第一个索引开始，并将前一个元素添加到当前数组元素以准备前缀数组。
步骤 4 - 接下来，开始遍历字符串，并根据 'arr' 元素的值增加每个字符的值。
步骤 5 - 在循环中对数组元素取模 26。
步骤 6 - 如果 arr[p] + alpha[p] 大于 'z'，则将 arr[p] - 26 添加到 alpha[p]。否则，仅将 arr[p] 添加到 alpha[p]。
步骤 7 - 返回更新后的 alpha 字符串。
示例
让我们使用示例输入调试下面的示例，以了解其工作原理。
最初，数组 arr 为 [0, 0, 0, 0, 0, 0, 0]。
数组"arr"具有基于 0 的索引。前缀数组包含 1 到字符串长度之间的元素。因此，我们可以说，在执行 prexies[p] 操作时，我们需要将字符串字符递增到 prefixes[p] - 1 索引。在每个操作中，我们总是需要递增第一个元素，因为前缀包含 1 到字符串长度范围内的元素。因此，我们在每次迭代中增加 arr[0]。
在前缀数组迭代之后，arr 将为 [6, -1, -1, -2, -2, 0, 0]。
下一步，我们将前一个元素添加到当前数组元素。因此，arr 将为 [6, 5, 4, 2, 2, 2, 2]。
接下来，取前 4 个元素并循环增加字符串字符。
#include <bits/stdc++.h>
using namespace std;
string getFinalString(string alpha, int pref_array[], int pref_len) {
// 数组初始化为 0
int arr[pref_len + 1] = { 0 };
// 根据前缀数组值更新数组
for (int p = 0; p < pref_len; p++) {
arr[pref_array[p]] -= 1;
arr[0] += 1;
}
// 创建前缀数组
for (int p = 1; p < pref_len; p++) {
arr[p] += arr[p - 1];
}
// 循环改变字符
for (int p = 0; p < pref_len; p++) {
arr[p] = (arr[p]) % 26;
if (arr[p] + alpha[p] > 'z')
alpha[p] = (alpha[p] + arr[p] - 26);
else
alpha[p] = alpha[p] + arr[p];
}
return alpha;
}
int main() {
string alpha = "aabc";
int prefixes[] = { 1, 2, 3, 4, 4, 3 };
int pref_len = sizeof(prefixes) / sizeof(prefixes[0]);
cout << "The final string is " << getFinalString(alpha, prefixes, pref_len) << endl;
return 0;
}
输出
The final string is gffe
时间复杂度 – 遍历数组和字符串的复杂度为 O(N)。
空间复杂度 – 将元素存储在前缀数组中的复杂度为 O(N)。
我们使用两种方法来查找增加字符串前缀字符后的结果字符串。第一种方法遍历每个数组元素并更新字符串前缀。第二种方法更合乎逻辑，因为我们同时创建前缀数组和增加字符，而不是在每个操作中增加多次。
