Java Solution using Trie. No need to sort.


  • 2
    I
    public class FileSystem {
        
        class Node {
            int type = 0; // 1 - dir ; 2 - file
            StringBuilder content;
            Node [] children = new Node[27];
        }
        
        Node root;
    
        public FileSystem() {
            root = new Node();
            root.type = 1;
            root.children[26] = new Node();
        }
        
        Node traverse(String s, int type) {
            Node node = root;
            for (int i = 0; i < s.length(); i++) {
                int next = s.charAt(i) == '/' ? 26 : s.charAt(i) - 'a';
                if (node.children[next] == null) {
                    node.children[next] = new Node();
                }
                node = node.children[next];
                if (i + 1 < s.length() && s.charAt(i + 1) == '/') {
                    node.type = 1;
                }
            }
            if (node.type == 0) {
                node.type = type;
            }
            return node;
        }
       
        void dfs(List<String> list, Node root, StringBuilder sb) {
            if (root.type > 0) {
                list.add(sb.toString());
            }
            for (int i = 0; i < 26; i++) {
                if (root.children[i] != null) {
                    sb.append((char)('a' + i));
                    dfs(list, root.children[i], sb);
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
        }
        
        public List<String> ls(String path) {
            List<String> list = new ArrayList<>();
            if ("/".equals(path)) {
                dfs(list, root.children[26], new StringBuilder());
                return list;
            }
            
            Node node = traverse(path, 1);
    
            if (node.type == 2) {
                int k = path.length() - 1;
                while (k >= 0 && path.charAt(k) != '/') {
                    k--;
                }
                list.add(path.substring(k + 1));
            } else {
                if (node.children[26] == null) {
                    return list;
                }
                dfs(list, node.children[26], new StringBuilder());
            }
            return list;
        }
        
        public void mkdir(String path) {
            traverse(path, 1);
        }
        
        public void addContentToFile(String filePath, String content) {
            Node node = traverse(filePath, 2);
            if (node.content == null) {
                node.content = new StringBuilder();
            }
            node.content.append(content);
        }
        
        public String readContentFromFile(String filePath) {
            Node node = traverse(filePath, 2);
            if (node.content == null) {
                return "";
            }
            return node.content.toString();
        }
    }
    

  • 0
    0

    Translated to C#:

    public class FileSystem 
    {
        enum PathTypes
        {
            File,
            Folder
        }
        
        class Node
        {
            internal PathTypes? type = null;
            // StringBuilder for better append performance
            internal StringBuilder content;
            // 26 for letters 1 for /
            internal Node[] children = new Node[27];
        }
        
        private Node root;
        
        public FileSystem() 
        {
            // initialize root folder /
            root = new Node();
            root.type = PathTypes.Folder;
            root.children[26] = new Node();
        }
        
        public IList<string> Ls(string path) 
        {
            List<string> list = new List<string>();
            if (path.Equals("/"))
            {
                Dfs(list, root.children[26], new StringBuilder());
                return list;
            }
            
            Node node = Traverse(path, PathTypes.Folder);
            
            if (node.type == PathTypes.File)
            {
                int k = path.Length - 1;
                // find the last folder path (not including the file path)
                while (k >= 0 && path[k] != '/')
                {
                    k--;
                }
                
                list.Add(path.Substring(k + 1));
            }
            else
            {
                if (node.children[26] == null)
                {
                    return list;
                }
                Dfs(list, node.children[26], new StringBuilder());
            }
            
            return list;
        }
        
        public void Mkdir(string path) 
        {
            Traverse(path, PathTypes.Folder);
        }
        
        public void AddContentToFile(string filePath, string content) 
        {
            Node node = Traverse(filePath, PathTypes.File);
            if (node.content == null)
            {
                node.content = new StringBuilder();
            }
            node.content.Append(content);
        }
        
        public string ReadContentFromFile(string filePath) 
        {
            Node node = Traverse(filePath, PathTypes.File);
            if (node.content == null)
            {
                return "";
            }
            
            return node.content.ToString();
        }
        
        private Node Traverse(string s, PathTypes type)
        {
            Node node = root;
            for (var i = 0; i < s.Length; i++)
            {
                int next = s[i] == '/' ? 26 : s[i] - 'a';
                if (node.children[next] == null)
                {
                    node.children[next] = new Node();
                }
                
                node = node.children[next];
                
                if (i + 1 < s.Length && s[i + 1] == '/')
                {
                    node.type = PathTypes.Folder;
                }
            }
            
            if (node.type == null)
            {
                node.type = type;
            }
            
            return node;
        }
        
        private void Dfs(List<string> list, Node root, StringBuilder sb)
        {
            if (root.type != null)
            {
                list.Add(sb.ToString());
            }
            
            for (var i = 0; i < 26; i++)
            {
                if (root.children[i] != null)
                {
                    sb.Append((char)('a' + i));
                    Dfs(list, root.children[i], sb);
                    // remove the last character
                    sb.Length--;
                }
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.