LeetCode/cs/remove-sub-folders-from-the-filesystem.cs

public class Solution {
    private class Trie<T> {
        public class TrieNode {
            public bool Has;
            public Dictionary<T, TrieNode> Successors;

            public TrieNode() {
                Has = false;
                Successors = new Dictionary<T, TrieNode>();
            }
        }

        public TrieNode Root = new TrieNode();

        public void Add(IEnumerable<T> path) {
            var node = Root;
            foreach (var element in path) {
                if (!node.Successors.ContainsKey(element)) {
                    node.Successors[element] = new TrieNode();
                }
                node = node.Successors[element];
            }
            node.Has = true;
        }
    }

    private void Reconstruct(
        List<string> result, List<string> path, Trie<string>.TrieNode node
    ) {
        if (node == null) {
            return;
        }

        if (node.Has) {
            result.Add(String.Join("/", path));
            return;
        }

        foreach (var subdirectory in node.Successors) {
            path.Add(subdirectory.Key);
            Reconstruct(result, path, subdirectory.Value);
            path.RemoveAt(path.Count - 1);
        }
    }

    public IList<string> RemoveSubfolders(string[] folder) {
        var trie = new Trie<string>();
        foreach (var entry in folder) {
            trie.Add(entry.Split("/"));
        }

        var result = new List<string>();
        Reconstruct(result, new List<string>(), trie.Root);
        return result;
    }
}