1593年。文字列を最大數(shù)の一意の部分文字列に分割します

難易度: 中

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

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

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

部分文字列は、文字列內(nèi)の連続した文字のシーケンスです。

例 1:

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

例 2:

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

例 3:

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

制約:

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

ヒント:

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

解決策:

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

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

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

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

<?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. 関數(shù)シグネチャ: メイン関數(shù)は maxUniqueSplit で、バックトラック プロセスを初期化します。

2. バックトラック:

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

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

複雑

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

連絡(luò)先リンク

このシリーズが役立つと思われた場(chǎng)合は、GitHub で リポジトリ にスターを付けるか、お?dú)荬巳毪辘违僵`シャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場(chǎng)合は、お?dú)葺Xにフォローしてください:

• LinkedIn
• GitHub

以上が文字列を最大數(shù)の一意の部分文字列に分割するの詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國(guó)語(yǔ) Web サイトの他の関連記事を參照してください。