Easy to understand 4ms Java solution without stack


  • 0
    K

    The idea :

    1. len of path at current level = len of path at [current level - 1] + len of current string + 1; // add 1 because you have to count "/" in the path unless current level is the root.
    2. Also, note that because the way the input is given you will reach the files that contain a "." in sequence. This is helpful because :
    dir
     firstsubdir
          file1.ext
     secondsubdir 
          file2.ext
    

    You don't need to save the length of "firstsubdir" once you have finished processing file1.ext. So, you can use the same index of an array to update the length at a given level.

    public class Solution {
        public int lengthLongestPath(String input) {
            int maxLen = 0;
            int [] dp = new int[input.length()];
            String [] ip = input.split("\n");
            dp[0] = ip[0].length();
            for(String s : ip){
                    int currentLevel = s.lastIndexOf("\t") + 1;
                    String cur = s.substring(currentLevel);
                    if(currentLevel > 0)
                      dp[currentLevel] = cur.length() + dp[currentLevel - 1] + 1;
                    else dp[currentLevel] = cur.length();  
                    if(cur.contains("."))
                       maxLen = Math.max(dp[currentLevel],maxLen);
                
            }
            return maxLen;
        }
    }
    

Log in to reply
 

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