JAVA O(n) 4 ms dynamic programming solution


  • 0
    G
    public class Solution {
        public int lengthLongestPath(String input) {
            String[] lines = input.split("\n");
            
            int max = Integer.MIN_VALUE;
            
            int[] dp = new int[lines.length];
            String[] names = new String[lines.length];
            
            for(String line: lines) {
            	String name = "";
            	int level = 0;
            	for(int i = 0; i < line.length(); i++) {
            		if(line.charAt(i) == '\t') {
            			level++;
            		} else {
            			name = line.substring(i);       			
            			break;
            		}
            	}
            	
            	dp[level] = name.length() + ((level == 0) ? 0 : dp[level - 1] + 1);
            	names[level] = name;
            	if(name.indexOf('.') != -1) {
                	max = Math.max(max, dp[level]);
            	}
            }
            
    		return max == Integer.MIN_VALUE ? 0 : max;        
        }
    }
    
    

  • 0
    S

    Very elegant solution


Log in to reply
 

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