文字列にスペースを追加する

2109年。文字列にスペースを追加する

難易度: 中

トピック: 配列、2 つのポインター、文字列、シミュレーション

0 から始まるインデックスの文字列 s と、スペースが追加される元の文字列内のインデックスを記述する 0 から始まるインデックスの整数配列 space が与えられます。各スペースは、指定されたインデックスの文字の前に挿入する必要があります。

• たとえば、s = "EnjoyYourCoffee" およびスペース = [5, 9] の場合、それぞれインデックス 5 と 9 にある 'Y' と 'C' の前にスペースを置きます。したがって、「Enjoy Your Coffee」を取得します。

スペースが追加された後の変更された文字列を返します。

例 1:

• 入力: s = "LeetcodeHelpsMeLearn"、スペース = [8,13,15]
• 出力: 「Leetcode は学習に役立ちます」
• 説明: インデックス 8、13、および 15 は、「LeetcodeHelpsMeLearn」の下線付きの文字に対応します。
  次に、それらの文字の前にスペースを置きます。

例 2:

• 入力: s = "icodeinpython"、スペース = [1,5,7,9]
• 出力: "Python でコードを記述します"
• 説明: インデックス 1、5、7、9 は、「icodeinpython」の下線付きの文字に対応します。
  次に、それらの文字の前にスペースを置きます。

例 3:

• 入力: s = "間隔"、スペース = [0,1,2,3,4,5,6]
• 出力: 「間隔」
• 説明: 文字列の最初の文字の前にスペースを置くこともできます。

制約:

1 5 s は英小文字と大文字のみで構成されます。
1 5 0 スペースのすべての値は
• 厳密に増加しています。

ヒント:

変更された文字列として、最初は空の新しい文字列を作成します。元の文字列を反復処理し、元の文字列の各文字を新しい文字列に追加します。ただし、前にスペースが必要な文字に到達するたびに、文字を追加する前にスペースを追加してください。
スペースの位置のインデックスの配列はソートされているため、ポインターを使用してスペースを配置する次のインデックスを追跡します。スペースが追加された場合のみ、ポインタをインクリメントします。
追加操作が O(1) で実行できることを確認してください。

解決策:

2 つのポインターを使用した効率的なアプローチを使用できます。 PHP 5.6 での実装は次のようになります:

解決策の説明:

1. ポインター spaceIndex を使用して、space 配列内の現在位置を追跡します。
2. ループを使用して文字列 s を反復処理します。
3. 文字列内の現在のインデックスがスペース配列内の現在の値と一致するかどうかを確認します。存在する場合は、結果にスペースを追加し、spaceIndex ポインタを前方に移動します。
4. 文字列の現在の文字を結果に追加します。
5. 最終結果を単一の文字列として返します。

このアプローチにより、スペース配列のソート順を利用して入力を効率的に処理できます。

このソリューションを PHP で実装してみましょう: 2109。文字列へのスペースの追加

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

// Example 1
$s1 = "LeetcodeHelpsMeLearn";
$spaces1 = [8, 13, 15];
echo addSpaces($s1, $spaces1) . "\n"; // Output: "Leetcode Helps Me Learn"

// Example 2
$s2 = "icodeinpython";
$spaces2 = [1, 5, 7, 9];
echo addSpaces($s2, $spaces2) . "\n"; // Output: "i code in py thon"

// Example 3
$s3 = "spacing";
$spaces3 = [0, 1, 2, 3, 4, 5, 6];
echo addSpaces($s3, $spaces3) . "\n"; // Output: " s p a c i n g"
?>

説明：

1. 効率的な追加: 。 PHP の演算子は、文字列を効率的に追加するために使用されます。
2. 2 つのポインター: spaceIndex ポインターは、space 配列を 1 回だけ処理することを保証します。
3. 時間計算量:
   • 文字列の反復処理には O(n) がかかります。n は文字列の長さです。
   • スペース配列ポインタとの照合には O(m) がかかります。m はスペース配列の長さです。
   • 組み合わせ: O(n m)、制約を考慮すると最適です。

このソリューションは制約を遵守しており、大きな入力に対しても効率的です。

連絡先リンク

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

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

• LinkedIn
• GitHub

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