Java Stack and dp Solution


  • 2

    Stack Solution

        public int lengthLongestPath(String input) {
            
            int max = 0;
            String[] dirs = input.split("\n");
            Deque<Integer> stack = new ArrayDeque<>(); // stores the length of dir/file till the current level
            
            for(int i = 0; i < dirs.length; i++) {
                
                int level = dirs[i].lastIndexOf('\t')+1;
                int curLen = dirs[i].length()-level+1;// we treat it as dir/
                
                while(level < stack.size()) {
                    stack.pop();
                }
                
                if(!stack.isEmpty()) {
                    curLen += stack.peek();
                }
                stack.push(curLen);
                
                if(dirs[i].contains(".")) {
                    max = Math.max(max, stack.pop()-1);
                }
            }
            
            return max;
        }
    

    dp solution

        public int lengthLongestPath(String input) {
            
            //dynamic programming
            
            int maxLen = 0;
            String[] dirs = input.split("\n");
            int[] dp = new int[dirs.length]; // length at each level, we can have dirs.length level at most
            
            for(int i = 0; i < dirs.length; i++) {
                
                String dir = dirs[i];
                int level = dir.lastIndexOf('\t') + 1; //could it be '\t'?
                
                dp[level] = dir.length() - level+1;
                if(level - 1 >= 0) {
                    dp[level] += dp[level-1];
                }
                
                if(dir.contains(".")) {
                    maxLen = Integer.max(maxLen, dp[level]-1);
                }
            }
            
            return maxLen;
        }
    

Log in to reply
 

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