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

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

難易度: 中

トピック: 配列、文字列、深さ優先検索、トライ

フォルダーのリストが与えられた場合、それらのフォルダー内のすべての サブフォルダーを削除した後でフォルダーを返します。回答は任意の順序で返すことができます。

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

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

• たとえば、「/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」内にあります。

例 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. フォルダーを辞書順に並べ替えます。
2. 現在の要素を配列に挿入し、そのサブフォルダーがすべて削除されるまでループし、要素がなくなるまでこれを繰り返します。

解決策:

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

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

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

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

このソリューションを 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() 関数はフォルダーを辞書順に並べます。これにより、サブフォルダーは親フォルダーを直接たどることになるため、サブフォルダーの関係を見つけやすくなります。

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

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

3. Result: この関数は、サブフォルダーを除き、ルート フォルダーのみを含む結果を返します。

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

連絡先リンク

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

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

• LinkedIn
• GitHub

以上がファイルシステムからサブフォルダーを削除するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。