文字列を最大数の一意の部分文字列に分割する

1593年。文字列を最大数の一意の部分文字列に分割します

難易度: 中

トピック: ハッシュ テーブル、文字列、バックトラッキング

文字列 s を指定すると、指定された文字列を分割できる一意の部分文字列の最大数を返します。

文字列 s を 空でない部分文字列 の任意のリストに分割できます。部分文字列の連結が元の文字列を形成します。ただし、すべての部分文字列が一意になるように部分文字列を分割する必要があります。

部分文字列は、文字列内の連続した文字のシーケンスです。

例 1:

• 入力: s = "ababccc"
• 出力: 5
• 説明: 最大限に分割する方法の 1 つは ['a', 'b', 'ab', 'c', 'cc'] です。 'a' と 'b' が複数回存在するため、['a', 'b', 'a', 'b', 'c', 'cc'] のような分割は無効です。

例 2:

• 入力: s = "aba"
• 出力: 2
• 説明: 最大限に分割する 1 つの方法は ['a', 'ba'] です。

例 3:

• 入力: s = "aa"
• 出力: 1
• 説明: 文字列をこれ以上分割することはできません。

制約:

• 1
• s には小文字の英字のみが含まれます。

ヒント:

1. セットを使用して、どの部分文字列がすでに使用されているかを追跡します
2. すべての位置で可能な各部分文字列を試し、完全な分割が不可能な場合はバックトラックします

解決策:

後戻りアプローチを使用できます。これには、文字列内の現在位置から部分文字列の作成を再帰的に試行し、これまでに使用した一意の部分文字列を追跡することが含まれます。

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

1. 再帰関数: 文字列の現在のインデックスから開始して、考えられるすべての部分文字列を探索する関数を作成します。
2. 一意性を設定する: セット (または PHP の配列) を使用して、現在の再帰パスで使用されている一意の部分文字列を追跡します。
3. バックトラッキング: 部分文字列が選択されたら、次の部分文字列の選択を続けることができます。繰り返さないとそれ以上の部分文字列を形成できない点に達した場合は、後戻りします。
4. 基本ケース: 文字列の終わりに到達すると、形成された一意の部分文字列をカウントします。

このソリューションを PHP で実装してみましょう: 1593。文字列を最大数の一意の部分文字列に分割します

<?php class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function maxUniqueSplit($s) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param $s
     * @param $used
     * @param $start
     * @return int|mixed
     */
    private function backtrack($s, $used, $start) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Example usage
$solution = new Solution();
echo $solution->maxUniqueSplit("ababccc"); // Output: 5
echo "\n";
echo $solution->maxUniqueSplit("aba"); // Output: 2
echo "\n";
echo $solution->maxUniqueSplit("aa"); // Output: 1
?>

説明：

1. 関数シグネチャ: メイン関数は maxUniqueSplit で、バックトラック プロセスを初期化します。

2. バックトラック:

   • バックトラック関数は、文字列、使用された部分文字列の配列、および現在の開始インデックスを受け取ります。
   • 開始インデックスが文字列の末尾に達すると、収集された一意の部分文字列の数を返します。
   • ループは、可能な終了インデックスを反復処理して、開始インデックスから部分文字列を作成します。
   • 部分文字列が一意である場合 (used 配列にまだ存在していない)、それが used に追加され、関数は次のインデックスに対して再帰的に実行されます。
   • そのパスを探索した後、部分文字列を削除してバックトラックし、他の可能性を探索します。

3. 出力: この関数は、さまざまな入力文字列の一意の部分文字列の最大数を返します。

複雑

• バックトラックの性質上、特に長い文字列の場合、時間の複雑さは高くなる可能性がありますが、制約 (最大長 16) を考慮すると、このソリューションは入力制限に対して十分に効率的です。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が文字列を最大数の一意の部分文字列に分割するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。