Remove Sub-Folders from the Filesystem solution and explanation

def removeSubfolders(folder):
    folder.sort()
    res = []
    prev = ""
    for f in folder:
        if not f.startswith(prev):
            res.append(f)
            prev = f + "/"
    return res

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);
        List<String> res = new ArrayList<>();
        String prev = "";
        for (String f : folder) {
            if (!f.startsWith(prev)) {
                res.add(f);
                prev = f + "/";
            }
        }
        return res;
    }
}

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

vector<string> removeSubfolders(vector<string>& folder) {
    sort(folder.begin(), folder.end());
    vector<string> res;
    string prev = "";
    for (const string& f : folder) {
        if (f.find(prev) != 0) {
            res.push_back(f);
            prev = f + "/";
        }
    }
    return res;
}

function removeSubfolders(folder) {
    folder.sort();
    const res = [];
    let prev = "";
    for (const f of folder) {
        if (!f.startsWith(prev)) {
            res.push(f);
            prev = f + "/";
        }
    }
    return res;
}

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Solution:
    def removeSubfolders(self, folder):
        root = TrieNode()
        for path in sorted(folder):
            node = root
            is_subfolder = False
            for part in path.split('/')[1:]:
                if part not in node.children:
                    node.children[part] = TrieNode()
                node = node.children[part]
                if node.is_end:
                    is_subfolder = True
                    break
            if not is_subfolder:
                node.is_end = True
        res = []
        def dfs(node, path):
            if node.is_end:
                res.append('/' + '/'.join(path))
                return
            for part, child in node.children.items():
                dfs(child, path + [part])
        dfs(root, [])
        return res

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

class TrieNode {
public:
    unordered_map<string, TrieNode*> children;
    bool isEnd;
    TrieNode() : isEnd(false) {}
};

void insert(TrieNode* root, const string& path) {
    TrieNode* node = root;
    istringstream stream(path);
    string part;
    while (getline(stream, part, '/')) {
        if (part.empty()) continue;
        if (!node->children.count(part))
            node->children[part] = new TrieNode();
        node = node->children[part];
        if (node->isEnd) return;
    }
    node->isEnd = true;
}

void collect(TrieNode* node, string path, vector<string>& result) {
    if (node->isEnd) {
        result.push_back(path);
        return;
    }
    for (auto& [part, child] : node->children) {
        collect(child, path + "/" + part, result);
    }
}

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        sort(folder.begin(), folder.end());
        TrieNode* root = new TrieNode();
        for (const auto& path : folder) {
            insert(root, path);
        }
        vector<string> result;
        collect(root, "", result);
        return result;
    }
};

function removeSubfolders(folder: string[]): string[] {
    let s = folder[1];
    return folder.sort().filter(x => !x.startsWith(s + '/') && (s = x));
}

func removeSubfolders(folder []string) []string {
	sort.Strings(folder)
	ans := []string{folder[0]}
	for _, f := range folder[1:] {
		m, n := len(ans[len(ans)-1]), len(f)
		if m >= n || !(ans[len(ans)-1] == f[:m] && f[m] == '/') {
			ans = append(ans, f)
		}
	}
	return ans
}

class Trie {
    children: Record<string, Trie>;
    fid: number;

    constructor() {
        this.children = {};
        this.fid = -1;
    }

    insert(i: number, f: string): void {
        let node: Trie = this;
        const ps = f.split('/');
        for (let j = 1; j < ps.length; ++j) {
            const p = ps[j];
            if (!(p in node.children)) {
                node.children[p] = new Trie();
            }
            node = node.children[p];
        }
        node.fid = i;
    }

    search(): number[] {
        const ans: number[] = [];
        const dfs = (root: Trie): void => {
            if (root.fid !== -1) {
                ans.push(root.fid);
                return;
            }
            for (const child of Object.values(root.children)) {
                dfs(child);
            }
        };
        dfs(this);
        return ans;
    }
}

function removeSubfolders(folder: string[]): string[] {
    const trie = new Trie();
    for (let i = 0; i < folder.length; ++i) {
        trie.insert(i, folder[i]);
    }
    return trie.search().map(i => folder[i]);
}

type Trie struct {
	children map[string]*Trie
	fid      int
}

func newTrie() *Trie {
	return &Trie{map[string]*Trie{}, -1}
}

func (this *Trie) insert(fid int, f string) {
	node := this
	ps := strings.Split(f, "/")
	for _, p := range ps[1:] {
		if _, ok := node.children[p]; !ok {
			node.children[p] = newTrie()
		}
		node = node.children[p]
	}
	node.fid = fid
}

func (this *Trie) search() (ans []int) {
	var dfs func(*Trie)
	dfs = func(root *Trie) {
		if root.fid != -1 {
			ans = append(ans, root.fid)
			return
		}
		for _, child := range root.children {
			dfs(child)
		}
	}
	dfs(this)
	return
}

func removeSubfolders(folder []string) (ans []string) {
	trie := newTrie()
	for i, f := range folder {
		trie.insert(i, f)
	}
	for _, i := range trie.search() {
		ans = append(ans, folder[i])
	}
	return
}