java solution 5ms, I don't know if it is exactly dp?


  • 0
    R
    public class Solution {
        public int lengthLongestPath(String input) {
            if(input==null||input.length()==0) return 0;
            String[] inputs = input.split("\n");
            if(inputs.length==1) return isFile(input)?input.length():0;
            int ret = 0;
            int[] dic = new int[findIndex(input)+1];
            dic[0] = inputs[0].length();
            for(int i = 1;i<inputs.length;i++) {
                int index = findIndex(inputs[i]);
                String realPath = resolve(inputs[i],index);
                if(isFile(realPath)) {
                    //count
                    ret = Math.max(ret,count(dic,index)+realPath.length());//todo,resolve the length of path
                }else {
                    //fill in the dic
                    dic[index] = realPath.length();
                }
            }
            return ret;
        }
        
        
        
        /**
         * tools
         */
        private int count(int[] dic, int index) {
            int ret = 0;
            for(int i = 0;i<index;i++) {
                ret += dic[i];
            }
            //add extra '/' number, which equals index
            return ret+index;
        }
        
        
        //
        private boolean isFile(String realPath) {
            return realPath.indexOf(".")!=-1&&realPath.indexOf(".")!=realPath.length()-1;
        }
        
        //count '\t'
        private int findIndex(String str) {
            String match = "\t";
            int i = 0;
            while(str.indexOf(match)!=-1){
                i++;
                match += "\t";
            }
            return i;
        }
        
        //resolve the real path name, delete'\t'
        private String resolve(String str, int index){
            return str.substring(index);
        }
    }
    

Log in to reply
 

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