C++ 通过递增给定长度的前缀找到最终字符串

在这个问题中，我们需要增加数组中给定大小的多个前缀的每个字符。解决这个问题的朴素方法是获取数组中给定大小的每个前缀，并递增前缀的每个字符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到字符串长度之间的元素。因此，我们可以说在执行前缀[p]操作时，我们需要将字符串字符的值递增到前缀[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) {
   // 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;
}