C++でフォルダリストからサブフォルダを削除する方法

問題の概要

フォルダのリストが与えられたとき、その中に含まれるすべてのサブフォルダを取り除き、残ったフォルダを任意の順序で返すことを考えます。ここで、あるフォルダ folder[i] が別のフォルダ folder[j] の内部に位置している場合、folder[i] は folder[j] のサブフォルダとみなされます。パスは「/folder1/subfolder2/…」のような形式で表現されます。

入力例

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

出力例

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

この例では、「/myfolder/secondfolder」は「/myfolder」のサブフォルダ、「/another/document/extrafolder」は「/another/document」のサブフォルダに該当するため除外され、親となるフォルダだけが結果として残ります。

解決のアプローチ

この問題は、次の手順で効率よく解くことができます。

1. パスの長さに基づいてフォルダ配列をソートします。短いパスから順に処理することで、親フォルダが必ず先に登録されることになります。
2. すでに確認済みのフォルダを記録するためのマップ m と、結果を格納する配列 ans を用意します。
3. 各パスについて、「/」を区切り目としてセグメントごとに文字列 temp を構築しながら、その途中パスがマップ m に登録済みかどうかを順番にチェックします。
4. 途中のパスがすでに登録されていれば、現在のパスはそのフォルダのサブフォルダであるため、フラグを false にして走査を打ち切ります。
5. 最後まで親フォルダが見つからなかった場合のみ、そのパスを ans に追加し、マップ m にも登録します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    static bool cmp(string s,string x){
        return s.size()<x.size();
    }
    vector<string> removeSubfolders(vector<string>& f) {
        sort(f.begin(),f.end(),cmp);
        map <string,bool> m;
        vector <string> ans;
        for(int i =0;i<f.size();i++){
            string s= f[i];
            string temp="";
            bool flag = true;
            for(int j =0;j<s.size();){
                temp+=s[j];
                j++;
                while(j<s.size() && s[j]!='/'){
                    temp+=s[j];
                    j++;
                }
                if(m[temp]){
                    flag = false;
                    break;
                }
            }
            if(flag){
                ans.push_back(s);
                m[s]=true;
            }
        }
        return ans;
    }
};
main(){
    vector<string> v = {"/myfolder","/myfolder/secondfolder","/another/document","/another/document/extrafolder","/another/final"};
    Solution ob;
    print_vector(ob.removeSubfolders(v));
}

実行結果

入力

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

出力

[/myfolder, /another/final, /another/document]

出力の末尾にある余分なカンマは、検証用の出力関数 print_vector の仕様によるものです。実際の結果には影響ありません。

計算量の目安

• 時間計算量: ソートに O(n log n × L)、各パスの走査全体で O(n × L)。ここで n はフォルダ数、L は平均パス長です。
• 空間計算量: マップと結果配列の保存に O(n × L) 必要です。

補足:別のアプローチ

パスを辞書順にソートすれば、サブフォルダは必ず直前の親フォルダの直後に並ぶため、「直前の要素が現在のパスの接頭辞になっているか」を確認するだけで判定することもできます。この方法ではセグメントごとの分解が不要になり、コードがよりシンプルになります。