6ms Java Solution using Wrapper Class and DFS


  • 3
    public class Solution {
        public int lengthLongestPath(String input) {
            if(input == null || input.length() == 0) return 0;
            int[] res = new int[]{0};
            FileNode root = parseString(input);
            outputLongestPath(root, res);
            return res[0] == 0 ? 0 : res[0] - 1;
        }
    
        private FileNode parseString(String input) {
            FileNode root = new FileNode(null, null, 0, -1, true), curr = root;
            String[] files = input.split("\n");
            for(String file: files) {
                int index = 0, level = 0;
                FileNode newFile;
    
                // calculate the level
                while(index < file.length() && file.substring(index, index + 1).equals("\t")) {
                    level++;
                    index++;
                }
    
                // decide if it is a file
                boolean isFile = file.contains(".");
    
                // decide it is the children or brother
                if(level == curr.level) {       // brother
                    newFile = new FileNode(file.substring(index, file.length()),
                            curr.parent, file.length() - index + 1, level, isFile);
                    curr.parent.children.add(newFile);
                } else {                        // children
                    while(level != curr.level + 1) curr = curr.parent;
                    newFile = new FileNode(file.substring(index, file.length()),
                            curr, file.length() - index + 1, level, isFile);
                    curr.children.add(newFile);
                }
                curr = newFile;
            }
            return root;
        }
    
        private void outputLongestPath(FileNode root, int[] res) {
            if(!root.children.isEmpty()) {
                for(FileNode child: root.children) {
                    outputLongestPath(child, res);
                }
            } else {
                if(!root.isFile) return;
                int count = root.count;
                while(root.parent != null) {
                    count += root.parent.count;
                    root = root.parent;
                }
                res[0] = Math.max(res[0], count);
            }
        }
    
        class FileNode {
            String fileName;
            FileNode parent;
            List<FileNode> children;
            int count, level;
            boolean isFile;
    
            public FileNode(String fileName, FileNode parent, int count, int level, boolean isFile) {
                this.fileName = fileName;
                this.parent = parent;
                this.children = new ArrayList<>();
                this.count = count;
                this.level = level;
                this.isFile = isFile;
            }
        }
    }
    

  • 0
    R

    I made a tree and used DFS, too. Please have a look.

    public class Solution {
        
        protected class Node{
            String word;
            int numberOfTabs;
            Node parent;
            List<Node> children = new ArrayList<Node>();
            
            public Node(String wordIn, int tabsIn){
                word = wordIn;
                numberOfTabs = tabsIn;
            }
            
            public void addChildren(Node child){
                children.add(child);
            }
            
            public void setParent(Node papa){
                parent = papa;
            }
            
            public Node getParent(){
                return parent;
            }
        }
        
        public int lengthLongestPath(String input) {
            
            // if the file system does not have a file, return immediately
            if(!input.contains(".")){
                return 0;
            }
            Node root = null;
            Node curr = null;
            // start creating tree
            int left = 0; int right = 0; int currTabs = 0; int prevTabs = 0;
            while(right < input.length()){ 
                while(right < input.length() && input.charAt(right)!='\n'){
                    right++;
                } 
                String currWord = input.substring(left,right);
                //System.out.println(currWord + " "+ currTabs+" "+ prevTabs);
                right++;
                left = right;
                
                if(currTabs ==0){ // root
                    root = new Node(currWord, 0);
                    curr = root;
                }
                else{
                    Node node = new Node(currWord,currTabs);
                    if(currTabs > prevTabs){   
                    }
                    else if(currTabs == prevTabs){
                        curr = curr.getParent();
                        
                    }
                    else {
                        int diff = prevTabs - currTabs +1;
                        while(diff>0){
                            curr = curr.getParent();
                            diff--;
                        }
                    } 
                        curr.addChildren(node);
                        node.setParent(curr);
                        curr = node;
                }
                
                // calculate tabs
                while(right<input.length() && input.charAt(right)=='\t'){
                    right++;   
                }  
                prevTabs = currTabs;
                currTabs = right - left;
                left = right;         
            }
            
            
            return giveLength(root);
        }
        
        static int giveLength(Node root){
            System.out.println(root.word);
            if(root.word.contains(".")){
                //System.out.println(root.word);
                return root.word.length()+root.numberOfTabs;
            }
            int max = 0;
            for(int i=0; i<root.children.size();i++){
                max = Math.max(max,giveLength(root.children.get(i)));
            }   
            if(max ==0){
                return 0;
            }
                
            return max+root.word.length();
        }
        
    }
    

Log in to reply
 

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