LeetCode #1233 Remove Sub-Folders from the Filesystem

問題概要

入力値：folder ([string])
出力値：[string]
Given a list of folders folder, return the folders after removing all sub-folders in those folders. You may return the answer in any order.
問題のリンク

入力例

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]

解答例1

計算量：O(n)
Python

class Solution(object):
    def removeSubfolders(self, folder):
        """
        :type folder: List[str]
        :rtype: List[str]
        """
        folder.sort(key=len)
        result = set()
        for name in folder:
            parts = name.split("/")
            parent_dir = ""
            for part in parts[1:]:
                parent_dir += "/" + part
                if parent_dir in result:
                    break
            else:
                result.add(parent_dir)
        return list(result)

Runtime: 66ms
Beats: 82.76%