Java O(n) stack solution


  • 0
    G
    public int lengthLongestPath(String input) {
    
        if(input.indexOf(".") == -1){
            return 0;
        }
        
        if(input.indexOf("\n") == -1){
            return input.length();
        }
        
        
        Stack<Integer> paths = new Stack<Integer>();
        int prevDepth = 0;
        int maxLength = 0;
        int curLength = 0;
        
        int index = input.indexOf("\n");
        curLength = index;
        paths.push(curLength);
        
        while(index < input.length()){
            int curDepth = 0;
            index++;
            
            while(input.charAt(index) == '\t'){
                curDepth++;
                index++;
            }
            int begin = index;
            
            boolean isFile = false;
            
            while(index < input.length()){
                if(input.charAt(index) == '.'){
                    isFile = true;
                    index++;
                }
                else if(input.charAt(index) == '\n'){
                    break;
                }
                else{
                    index++;
                }
            }
            
            int diff = curDepth - prevDepth;
            while(diff < 1){
                int tmp = paths.pop();
                curLength -= tmp;
                diff++;
            }
            
            int length = index - begin;
            if(curDepth > 0)            //this is to pass the disgusting test case, you know which one it is
                length++;
            curLength += length;
            prevDepth = curDepth;
            paths.push(length);
            
            if(isFile){
                maxLength = Math.max(curLength, maxLength);
            }
        }
        
        return maxLength;
    }

Log in to reply
 

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