1233。ファイルシステムからサブフォルダーを削除

難易度: 中

トピック: 配列、文字列、深さ優(yōu)先検索、トライ

フォルダーのリストが與えられた場(chǎng)合、それらのフォルダー內(nèi)のすべての サブフォルダーを削除した後でフォルダーを返します?；卮黏?strong>任意の順序で返すことができます。

フォルダー[i]が別のフォルダー[j]內(nèi)にある場(chǎng)合、そのサブフォルダーと呼ばれます。 folder[j] のサブフォルダは、folder[j] で始まり、その後に「/」が続く必要があります。たとえば、「/a/b」は「/a」のサブフォルダーですが、「/b」は「/a/b/c」のサブフォルダーではありません。

パスの形式は、「/」の後に 1 つ以上の小文字の英字が続く形式の 1 つ以上の文字列を連結(jié)したものです。

• たとえば、「/leetcode」と「/leetcode/problems」は有効なパスですが、空の文字列と「/」は有効ではありません。

例 1:

• 入力: フォルダー = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
• 出力: ["/a","/c/d","/c/f"]
• 説明: フォルダー「/a/b」は「/a」のサブフォルダーであり、「/c/d/e」はファイルシステムのフォルダー「/c/d」內(nèi)にあります。

例 2:

• 入力: フォルダー = ["/a","/a/b/c","/a/b/d"]
• 出力: ["/a"]
• 説明: フォルダー「/a/b/c」および「/a/b/d」は、「/a」のサブフォルダーであるため、削除されます。

例 3:

• 入力: フォルダー = ["/a/b/c","/a/b/ca","/a/b/d"]
• 出力: ["/a/b/c","/a/b/ca","/a/b/d"]

制約:

• 1 4
• 2
• フォルダー[i]には小文字と「/」のみが含まれます。
• フォルダー[i]は常に文字「/」で始まります。
• 各フォルダー名は一意です。

ヒント:

1. フォルダーを辭書(shū)順に並べ替えます。
2. 現(xiàn)在の要素を配列に挿入し、そのサブフォルダーがすべて削除されるまでループし、要素がなくなるまでこれを繰り返します。

解決策:

並べ替えと文字列比較を組み合わせて利用できます。以下の手順は、PHP でのソリューションの概要を示しています。

1. フォルダーを辭書(shū)順に並べ替えます: フォルダー パスを辭書(shū)順に並べ替えると、サブフォルダーがその親フォルダーのすぐ後に続くようになります。たとえば、並べ替えられたリストでは「/a」の後に「/a/b」が続くため、サブフォルダーの関係を簡(jiǎn)単に確認(rèn)できます。

2. サブフォルダーを特定して除外する: 並べ替えられたリストを反復(fù)処理して、現(xiàn)在のフォルダー パスが以前に追加したパスのサブフォルダーであるかどうかを確認(rèn)できます。そうであれば、スキップします。そうでない場(chǎng)合は、結(jié)果リストに追加します。

3. PHP でのソリューションの実裝: 結(jié)果リストに追加された最後のフォルダー パスを追跡します。現(xiàn)在のフォルダーがこの最後のフォルダーで始まり、その直後に / が続く場(chǎng)合、それはサブフォルダーであるため、無(wú)視する必要があります。

このソリューションを PHP で実裝してみましょう: 1233。ファイルシステムからサブフォルダーを削除

<?php
/**
 * @param String[] $folder
 * @return String[]
 */
function removeSubfolders($folders) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$folder1 = ["/a","/a/b","/c/d","/c/d/e","/c/f"];
$folder2 = ["/a","/a/b/c","/a/b/d"];
$folder3 = ["/a/b/c","/a/b/ca","/a/b/d"];

print_r(removeSubfolders($folder1)); // Output: ["/a","/c/d","/c/f"]
print_r(removeSubfolders($folder2)); // Output: ["/a"]
print_r(removeSubfolders($folder3)); // Output: ["/a/b/c","/a/b/ca","/a/b/d"]
?>

説明：

1. 並べ替え: sort() 関數(shù)はフォルダーを辭書(shū)順に並べます。これにより、サブフォルダーは親フォルダーを直接たどることになるため、サブフォルダーの関係を見(jiàn)つけやすくなります。

2. 各フォルダーをループします:

   • 結(jié)果が空 (最初の反復(fù)) である場(chǎng)合、または現(xiàn)在のフォルダー パスが最後に追加されたフォルダーで始まり、その後に / が続いていない場(chǎng)合、そのフォルダーはサブフォルダーではないため、結(jié)果の配列に追加されます。
   • 最後のフォルダー パスで始まり、直後に / がある場(chǎng)合、それはサブフォルダーであるため、結(jié)果への追加をスキップします。

3. Result: この関數(shù)は、サブフォルダーを除き、ルート フォルダーのみを含む結(jié)果を返します。

このアプローチは、並べ替えステップにより時(shí)間計(jì)算量が O(n log n) で効率的であり、リニア スキャンは O(n )。これは、問(wèn)題の制約內(nèi)でより大きな入力に対する優(yōu)れた解決策となります。

連絡(luò)先リンク

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

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

• LinkedIn
• GitHub

以上がファイルシステムからサブフォルダーを削除するの詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國(guó)語(yǔ) Web サイトの他の関連記事を參照してください。