文字列圧縮 III

3163。文字列圧縮 III

難易度: 中

トピック: 文字列

指定された文字列ワードを次のアルゴリズムを使用して圧縮します:

• 空の文字列コンプから始めます。 word が空ではない場合は、次の操作を使用します。
  • 単一文字 c を 最大 9 回繰り返すことで構成される単語の最大長の接頭辞を削除します。
  • プレフィックスの長さに続いて c を comp に追加します。

文字列 comp を返します。

例 1:

• 入力: word = "abcde"
• 出力: "1a1b1c1d1e"
• 説明: 最初は、comp = "" です。各操作の接頭辞として「a」、「b」、「c」、「d」、および「e」を選択して、操作を 5 回適用します。
  • 各プレフィックスに、「1」の後に補完する文字を追加します。

例 2:

• 入力: word = "aaaaaaaaaaaaaabb"
• 出力: "9a5a2b"
• 説明: 最初は、comp = "" です。操作を 3 回適用し、各操作のプレフィックスとして「aaaaaaaa」、「aaaaa」、および「bb」を選択します。
  • 接頭辞「aaaaaaaa」の場合は、「9」の後に「a」を追加して補完します。
  • 接頭辞「aaaaa」の場合は、「5」の後に「a」を追加して補完します。
  • 接頭辞「bb」の場合は、「2」の後に「b」を追加して補完します。

制約:

• 1 2 * 105
word は英小文字のみで構成されています。

ヒント:

毎回、接頭語内の同じ文字を最大 9 回まで切り取るだけです。常に、より大きなプレフィックスを切り取る方が良いです。

解決策:

貪欲なアプローチを使用して、繰り返し文字の可能な限り長いプレフィックス (一度に 9 個まで) を取得し、そのプレフィックスの長さをその文字とともに結果に追加することで文字列を圧縮できます。

段階的な解決策は次のとおりです:

1. 変数の初期化

   :
   comp (圧縮文字列) は空の文字列として始まります。
   ポインターまたはインデックス i を使用して、単語内の位置を追跡します。

2. 単語をループします

   :
   Word に文字が残っている間に、9 文字を超えない、繰り返される文字の最長の接頭辞を見つけます。
   現在の文字が連続して繰り返される回数を最大 9 回まで数えます。

3. 圧縮文字列に追加

   :
   • カウントの後に、補完する文字を追加します。
   • 処理された文字数だけポインタを前に移動します。

4. 結果を返す:

   • 文字列全体を処理した後、圧縮された文字列を返します。

このソリューションを PHP で実装してみましょう: 3163。文字列圧縮 III

<?php
/**
 * @param String $word
 * @return String
 */
function compressString($word) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo compressString("abcde");          // Output: "1a1b1c1d1e"
echo "\n";
echo compressString("aaaaaaaaaaaaaabb"); // Output: "9a5a2b"
?>

説明：

• カウントループ: メインループ内で while ループを使用して、Word 内の各一意の文字ごとに連続する文字 (最大 9 個) をカウントします。
• 結果の追加: 各シーケンスをカウントした後、カウントと文字を直接コンプに追加します。
• ポインターの更新: メイン ループ ポインター i は、カウントされた文字数だけ前方に移動し、各反復で残りの文字列のサイズを効果的に削減します。

複雑さの分析

• 時間計算量: O(n)、n は単語の長さです。各文字は 1 回処理されます。
• 空間複雑度: comp. に格納された圧縮結果の O(n)

このソリューションは効率的で、9 文字未満のシーケンスや各文字の 1 回の出現などの特殊なケースを処理します。

連絡先リンク

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

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

• LinkedIn
• GitHub

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