透過遞增給定長度的字首查詢最終字串
在這個問題中,我們需要增加陣列中給定大小的多個字首的每個字元。解決這個問題的簡單方法是獲取陣列中給定大小的每個字首,並將字首的每個字元遞增 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) 用於將元素儲存在字首陣列中。
我們使用了兩種方法來查詢遞增字串字首字元後的結果字串。第一種方法遍歷每個陣列元素並更新字串字首。第二種方法更合乎邏輯,因為我們建立字首陣列並同時遞增字元,而不是在每個操作中多次遞增。