シフトする文字 II

2381。シフトする文字 II

難易度: 中

トピック: 配列、文字列、プレフィックス合計

英小文字の文字列 s と 2D 整数配列シフトが与えられます。ここで、shifts[i] = [start_i、end_i、direction_i]。すべての i について、s 内の文字をインデックス開始iからインデックス終了_i (_包括的) 方向シフトします。 🎜>i _{= 1、または方向}i _{= の場合は文字を後方にシフトします。 0.}

文字を

前方にシフトすることは、アルファベットの次の文字に置き換えることを意味します(「z」が「a」になるように折り返す)。同様に、文字を 後方 に移動することは、その文字をアルファベットの 前の 文字に置き換えることを意味します ('a' が 'z' になるように折り返す)。

s へのすべてのシフトが適用された後の最後の文字列を返します。

例 1:

• 入力: s = "abc"、シフト = [[0,1,0],[1,2,1],[0,2,1]]
• 出力:「エース」
• 説明: まず、文字をインデックス 0 からインデックス 1 に後方にシフトします。これで s = 「ザック」になります。
  次に、文字をインデックス 1 からインデックス 2 に前方にシフトします。これで s = "zbd".
  最後に、文字をインデックス 0 からインデックス 2 に前方にシフトします。これで、s = 「エース」となります。

例 2:

• 入力: s = "dztz"、シフト = [[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 つずつシフトすることは避ける必要があります。これは、大量の入力に対して遅すぎるためです。代わりに、

prefix sum と呼ばれる手法を活用することで、より最適なアプローチを使用できます。

手順:

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. Prefix Sum: シフト配列を反復処理し、シフトの累積合計を維持することにより、各文字の合計シフトを計算します。
4. 文字シフト: 文字列内の各文字について、式 (ord(currentChar) - ord('a') totalShift) % 26 を使用して最終的にシフトされた文字を計算します。これは、文字列の循環的な性質を説明します。アルファベット。
5. 戻り結果: 最終的な文字列は、文字配列を文字列に変換して返し、それを返すことによって取得されます。

時間計算量:

• 時間計算量: O(n m)、n は文字列 s の長さ、m はシフト数です。これは、文字列とシフトのリストをそれぞれ 1 回ずつ反復処理するためです。
• 空間計算量: O(n)、n はシフト配列に必要な空間のため、文字列 s の長さです。

このソリューションは、入力制約の上限があっても問題を効率的に処理します。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がシフトする文字 IIの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。