最长绝对文件路径——算法面试刷题1（google），字符串处理，使用tree遍历dfs类似思路

class Solution:
    """
    @param input: an abstract file system
    @return: return the length of the longest absolute path to file
    """
    def lengthLongestPath(self, input):
        # write your code here
        ans = 0
        path = []
        lines = input.split("\n")
        for line in lines:
            cnt = self.count_tab(line)
            path_name = self.get_path_name(line)
            if cnt < len(path):
                path[cnt] = path_name
            else:
                path.append(path_name)
            if self.is_file(path_name):
                length = len("/".join(path[:cnt+1])) 
                if length > ans: ans = length
        return ans
        
    def count_tab(self, s):
        return s.count("\t")
        
    def get_path_name(self, s):
        index = s.rfind("\t")
        if index >= 0:
            return s[index+1:] # +2 is error. \t is a char!!!
        else:
            return s
    
    def is_file(self, f):
        return f.find(".") >= 0

import re

class Solution:
    # @param {string} input an abstract file system
    # @return {int} return the length of the longest absolute path to file
    def lengthLongestPath(self, input):
        # Write your code here
        dict = collections.defaultdict(lambda: "")
        lines = input.split("\n")

        n = len(lines)
        result = 0
        for i in xrange(n):
            count = lines[i].count("\t")

            lines[i] = dict[count - 1] + re.sub("\\t+","/", lines[i])
            if "." in lines[i]:
                result = max(result, len(lines[i]))
            dict[count] = lines[i]

        return result