Remove Sub-Folders from the Filesystem ใน C++: ลบโฟลเดอร์ย่อย

โจทย์

กำหนดรายการพาธโฟลเดอร์ ลบโฟลเดอร์ย่อยทั้งหมด (โฟลเดอร์ที่อยู่ภายในอีกโฟลเดอร์หนึ่ง) คืนโฟลเดอร์ที่เหลือ

ตัวอย่าง: ["/myfolder","/myfolder/secondfolder","/another/document","/another/document/extrafolder","/another/final"] → ["/myfolder","/another/final","/another/document"]

แนวคิด: เรียงตามความยาว + Hash Set ตรวจสอบพ่อ

เรียงพาธจากสั้นไปยาว → พ่อจะมาก่อนลูกเสมอ ใช้ map/set บันทึกโฟลเดอร์ที่เป็น "ราก" ไว้

ขั้นตอน

1. เรียงอาร์เรย์พาธตามความยาวสตริง (สั้นก่อน)
2. สร้าง unordered_set<string> seen และ vector<string> ans
3. ลูปแต่ละพาธ s:
   • แยกพาธเป็นส่วนๆ โดย '/' → ตรวจสอบทุก prefix ว่าอยู่ใน seen หรือไม่
   • ถ้ามี prefix อยู่ใน seen → เป็น subfolder → ข้าม
   • ถ้าไม่มี → ใส่ s ลง ans และ seen

ตัวอย่างโค้ด C++ (ปรับปรุงให้ชัดเจนกว่าเดิม)

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<string> v) {
    cout << "[";
    for (auto& s : v) cout << s << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        sort(folder.begin(), folder.end(), [](const string& a, const string& b) {
            return a.size() < b.size();
        });
        
        unordered_set<string> seen;
        vector<string> ans;
        
        for (const string& path : folder) {
            bool isSub = false;
            string prefix = "";
            
            // ตรวจสอบทุก prefix ที่จบด้วย '/'
            for (int i = 1; i < path.size(); i++) {
                if (path[i] == '/') {
                    prefix = path.substr(0, i);
                    if (seen.count(prefix)) {
                        isSub = true;
                        break;
                    }
                }
            }
            
            if (!isSub) {
                ans.push_back(path);
                seen.insert(path);
            }
        }
        return ans;
    }
};

int main() {
    vector<string> v = {"/myfolder","/myfolder/secondfolder","/another/document","/another/document/extrafolder","/another/final"};
    Solution ob;
    print_vector(ob.removeSubfolders(v));
    return 0;
}

อินพุต / เอาต์พุต

Input: ["/myfolder","/myfolder/secondfolder","/another/document","/another/document/extrafolder","/another/final"]

Output: ["/myfolder", "/another/final", "/another/document"]

ความซับซ้อน

• Time: O(N log N + N × L) - เรียง + ตรวจ prefix (L = ความยาวพาธเฉลี่ย)
• Space: O(N × L)