Alih keluar Sub-Folder daripada Sistem Fail

1233. Alih keluar Sub-Folder daripada Sistem Fail

Kesukaran: Sederhana

Topik: Tatasusunan, Rentetan, Carian Pertama Kedalaman, Percubaan

Diberikan senarai folder folder, kembalikan folder selepas mengalih keluar semua sub-folder dalam folder tersebut. Anda boleh mengembalikan jawapan dalam sebarang pesanan.

Jika folder[i] terletak dalam folder lain[j], ia dipanggil sub-folder daripadanya. Subfolder folder[j] mesti bermula dengan folder[j], diikuti dengan "/". Contohnya, "/a/b" ialah subfolder bagi "/a", tetapi "/b" bukan subfolder bagi "/a/b/c".

Format laluan ialah satu atau lebih rentetan bentuk yang digabungkan: '/' diikuti dengan satu atau lebih huruf kecil Inggeris.

• Sebagai contoh, "/leetcode" dan "/leetcode/problems" ialah laluan yang sah manakala rentetan kosong dan "/" tidak.

Contoh 1:

• Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
• Output: ["/a","/c/d","/c/f"]
• Penjelasan: Folder "/a/b" ialah subfolder bagi "/a" dan "/c/d/e" berada di dalam folder "/c/d" dalam sistem fail kami.

Contoh 2:

• Input: folder = ["/a","/a/b/c","/a/b/d"]
• Output: ["/a"]
• Penjelasan: Folder "/a/b/c" dan "/a/b/d" akan dialih keluar kerana ia adalah subfolder bagi "/a".

Contoh 3:

• Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
• Output: ["/a/b/c","/a/b/ca","/a/b/d"]

Kekangan:

• 1 4
• 2
• folder[i] hanya mengandungi huruf kecil dan '/'.
• folder[i] sentiasa bermula dengan aksara '/'.
• Setiap nama folder adalah unik.

Petunjuk:

1. Isih folder mengikut leksikografi.
2. Masukkan elemen semasa dalam tatasusunan dan kemudian gelung sehingga kita menyingkirkan semua subfolder mereka, ulangi ini sehingga tiada unsur yang tinggal.

Penyelesaian:

Kami boleh menggunakan gabungan pengisihan dan perbandingan rentetan. Langkah-langkah di bawah menggariskan penyelesaian dalam PHP:

1. Isih Folder Secara Leksikografi: Mengisih laluan folder dalam susunan leksikografik memastikan mana-mana subfolder akan mengikuti folder induknya serta-merta. Contohnya, "/a" akan diikuti dengan "/a/b" dalam senarai diisih, membolehkan kami menyemak perhubungan subfolder dengan mudah.

2. Kenal pasti dan Tapis Sub-Folder: Kami boleh melelang melalui senarai yang diisih, menyemak sama ada laluan folder semasa ialah sub-folder daripada laluan yang ditambahkan sebelum ini. Jika ya, kami melangkaunya. Jika tidak, kami menambahkannya pada senarai keputusan kami.

3. Melaksanakan Penyelesaian dalam PHP: Kami menjejaki laluan folder terakhir yang ditambahkan pada senarai hasil. Jika folder semasa bermula dengan folder terakhir ini dan diikuti dengan serta-merta dengan /, ia adalah subfolder dan harus diabaikan.

Mari laksanakan penyelesaian ini dalam PHP: 1233. Alih keluar Sub-Folder daripada Sistem Fail

<?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"]
?>

Penjelasan:

1. Isih: Fungsi sort() menyusun folder dalam susunan leksikografik. Ini menjadikannya lebih mudah untuk mencari hubungan subfolder kerana subfolder akan mengikuti folder induknya secara langsung.

2. Gelung melalui setiap folder:

   • Jika hasil kosong (lelaran pertama) atau jika laluan folder semasa tidak bermula dengan folder terakhir ditambah diikuti dengan /, ia bukan subfolder dan ditambahkan pada tatasusunan hasil.
   • Jika ia bermula dengan laluan folder terakhir dan mempunyai / serta-merta mengikuti, ia adalah sub-folder dan kami melangkau menambahkannya ke hasil.

3. Hasil: Fungsi mengembalikan hasil, yang mengandungi hanya folder akar, tidak termasuk mana-mana subfolder.

Pendekatan ini cekap dengan kerumitan masa O(n log n) disebabkan oleh langkah pengisihan dan imbasan linear mempunyai O(n ), menjadikan ini penyelesaian yang baik untuk input yang lebih besar dalam kekangan masalah.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci Alih keluar Sub-Folder daripada Sistem Fail. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!