透過遞增給定長度的字首查詢最終字串


在這個問題中,我們需要增加陣列中給定大小的多個字首的每個字元。解決這個問題的簡單方法是獲取陣列中給定大小的每個字首,並將字首的每個字元遞增 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) 用於將元素儲存在字首陣列中。

我們使用了兩種方法來查詢遞增字串字首字元後的結果字串。第一種方法遍歷每個陣列元素並更新字串字首。第二種方法更合乎邏輯,因為我們建立字首陣列並同時遞增字元,而不是在每個操作中多次遞增。

更新於:2023年8月31日

92 次檢視

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告