移動字母 II

2381。移動字母 II

難度：中

主題：陣列、字串、前綴和

給定一個由小寫英文字母組成的字串s 和一個二維整數數組shifts，其中shifts[i] = [start_i, end_i, Direction_i]。對於每個i，shift s 中的字元從索引開始_i 到索引結束_i（包含）向前if 方向_i = 1，或如果方向_i =則向後移動字元0.

移動字元向前意味著將其替換為字母表中的下一個字母（環繞以使“z”變成“a”）。同樣，向後移動字元意味著將其替換為字母表中的前一個字母（環繞以使“a”變成“z”）。

傳回

套用所有此類轉換到 s 後的最終字串。

範例1：

• 輸入： s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]
• 輸出：「ace」
• 解釋： 首先，將索引 0 的字元向後移動到索引 1。現在 s =「札克」。
  其次，將字元從索引 1 向前移動到索引 2。現在 s =“zbd”。
  最後，將字元從索引 0 向前移動到索引 2。現在 s =“ace”。

範例2：

• 輸入： s = "dztz", shifts = [[0,0,0],[1,1,1]]
• 輸出：「catz」
• 說明：先將索引0處的字元向後移到索引0處。現在 s =“cztz”。
  最後，將字元從索引 1 向前移動到索引 1。現在 s =“catz”。

約束：

1 4 shifts[i].length == 3
0 i i 0 i s 由小寫英文字母組成。

提示：

您是否可以追蹤哪些字符被移動以及在所有班次中移動了多少字符，而不是在每個班次中移動每個字符？
嘗試標記每個班次的開始和​​結束，然後執行班次的前綴和。

解：

我們需要避免每次移位都將字元一個一個地移動，因為這對於大輸入來說太慢了。相反，我們可以利用稱為

前綴總和. 的技術來使用更最佳化的方法。

步驟：

1. 標記移位邊界：我們不是立即移位每個字符，而是在每個範圍的開始和結束處標記移位效果。
2. 應用前綴和：標記所有移位後，我們可以使用前綴和技術計算每個字元的累積移位。這使我們能夠有效地將累積移位應用於每個字元。
3. 執行移位：一旦我們知道每個字元的總移位，我們就可以將移位（向前或向後）應用於字串。

讓我們用 PHP 實作這個解：2381。移動字母 II

<?php /**
 * @param String $s
 * @param Integer[][] $shifts
 * @return String
 */
function shiftingLetters($s, $shifts) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test the function
$s1 = "abc";
$shifts1 = [[0, 1, 0], [1, 2, 1], [0, 2, 1]];
echo shiftingLetters($s1, $shifts1) . "\n";  // Output: "ace"

$s2 = "dztz";
$shifts2 = [[0, 0, 0], [1, 1, 1]];
echo shiftingLetters($s2, $shifts2) . "\n";  // Output: "catz"
?>

解釋：

1. 對於每個移位 [開始、結束、方向]，我們將在開始處遞增移位數組並在結束時遞減 1。這使我們能夠追蹤移位範圍的開始和結束。
2. 處理完所有移位後，我們對移位陣列套用前綴和，以獲得每個索引處的累積移位。
3. 最後，我們將累積移位套用於字串中的每個字元。

代碼說明：

1. 輸入解析：我們將輸入字串 s 轉換為字元數組，以便於操作。
2. 移位陣列：我們將大小為 n 1 的移位陣列初始化為零。此數組用於追蹤移位效果。對於每個班次 [開始、結束、方向]，我們調整 shift[start] 和 shift[end 1] 處的值以反映班次的開始和​​結束。
3. 前綴總和：我們透過迭代移位數組並維護移位的累積和來計算每個字元的總移位。
4. 字符移位：對於字串中的每個字符，我們使用公式(ord(currentChar) - ord('a')totalShift) % 26 計算最終的移位字符，這說明了字串的循環性質字母表。
5. 傳回結果：將字元陣列轉回字串並傳回，得到最終的字串。

時間複雜度：

• 時間複雜度：O(n m)，其中n是字串s的長度，m是移位次數。這是因為我們每次迭代字串和班次列表一次。
• 空間複雜度：O(n)，其中n是字串s的長度，因為移位陣列需要空間。

即使輸入約束有上限，此解決方案也能有效處理問題。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是移動字母 II的詳細內容。更多資訊請關注PHP中文網其他相關文章！