数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学通过递增给定长度的前缀查找最终字符串
在这个问题中，我们需要增加数组中给定大小的多个前缀的每个字符。解决这个问题的简单方法是获取数组中给定大小的每个前缀，并将前缀的每个字符递增 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'。
递增第一个字符后，字符串变为 'aaa'。
方法 1
在这种方法中，我们将遍历数组并获取长度为 prefixes[i] 的字符串前缀。之后，我们将遍历前缀字符串并将每个字符增加 1。
算法
步骤 1 − 使用 for 循环遍历数组 prefixes。
步骤 2 − 遍历从索引 0 到 prefixes[p] 的字符串。
步骤 3 − 如果字符串中索引处的字符为 'z'，则将字符更新为 'a'。否则，向字符添加 1。
步骤 4 − 完成所有循环迭代后，返回 alpha 字符串。
示例
#include <bits/stdc++.h>
using namespace std;
string getFinalString(string alpha, int pref_array[], int pref_len) {
// Traverse prefix array
for (int p = 0; p < pref_len; p++) {
// Incrementing the pref_array[p] elements cyclically
for (int q = 0; q < pref_array[p]; q++) {
// If the current character is 'z'
if (alpha[q] == 'z') {
alpha[q] = 'a';
} else {
// Increment character by 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 索引的字符串字符。在每个操作中，我们总是需要递增第一个元素，因为 prexies 包含 1 到字符串长度范围内的元素。因此，我们在每次迭代中递增 arr[0]。
在 prexies 数组迭代之后，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) {
// Array initialized with 0
int arr[pref_len + 1] = { 0 };
// Update the array according to the prefix array value
for (int p = 0; p < pref_len; p++) {
arr[pref_array[p]] -= 1;
arr[0] += 1;
}
// Create prefix array
for (int p = 1; p < pref_len; p++) {
arr[p] += arr[p - 1];
}
// Change character cyclically
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) 用于将元素存储在前缀数组中。
我们使用了两种方法来查找递增字符串前缀字符后的结果字符串。第一种方法遍历每个数组元素并更新字符串前缀。第二种方法更合乎逻辑，因为我们创建前缀数组并同时递增字符，而不是在每个操作中多次递增。
92 次查看
