力扣：1233. 删除子文件夹 题解（Java）

题目地址：1233.删除子文件夹

题目描述：

你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。

我们这样定义「子文件夹」：

                  如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 就是 folder[j] 的子文件夹。

文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：

/ 后跟一个或者多个小写英文字母。

例如，/leetcode 和 /leetcode/problems 都是有效的路径，而空字符串和 / 不是。

例1：

输入：folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
输出：["/a","/c/d","/c/f"]
解释："/a/b/" 是 "/a" 的子文件夹，而 "/c/d/e" 是 "/c/d" 的子文件夹。

例2：

输入：folder = ["/a","/a/b/c","/a/b/d"]
输出：["/a"]
解释：文件夹 "/a/b/c" 和 "/a/b/d/" 都会被删除，因为它们都是 "/a" 的子文件夹。

例3：

输入：folder = ["/a/b/c","/a/b/d","/a/b/ca"]
输出：["/a/b/c","/a/b/d","/a/b/ca"]

提示：

1. 1 <= folder.length <= 4 * 10^4
2. 2 <= folder[i].length <= 100
3. folder[i] 只包含小写字母和 /
4. folder[i] 总是以字符 / 起始
5. 每个文件夹名都是唯一的

解题思路：

1.一开始的思路是用两层循环，第一层循环遍历数组，第二层循环查找所有元素否存在它的子串、或者它是后面的某个元素的子串。但在运行过程中，出现一个数据量巨大的输入，导致运行超时。翻看评论区后，发现这道题其实要先排序，排完序后，所有的子文件夹都在其父文件夹的后面，这时只要遍历一遍数组就可以找到所有的父文件夹了。

2.判断两个字符串其中一个是否是另一个字符串的子串。String类中自带函数startsWith()可以判断字符串是否以特定的字符串开头，但判断/a/b，/a/bc时，结果与实际的要求不符合。因为字符串/a/bc虽然以/a/b开头，但这是两个不同的文件夹。所以给/a/b后面加一个 / ，如果是/a/b的子文件夹，那么路径肯定以/a/b/开头。

代码：

class Solution {
    public List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);//对字符串数组排序
        List<String> ans = new ArrayList<String>();//新建一个List存储父文件夹
        int flag = 0;//临时存储父文件夹的下标
        ans.add(folder[0]);//将数组第一个元素存入List中，因为第一个肯定是父文件夹
        for(int i =1; i < folder.length; i++){
            if(!folder[i].startsWith(folder[a]+"/")){
            //判断数组存储的文件夹路径是否是当前标记的文件夹的子文件夹，是，就继续判断后面的数据
            //不是，则记录这个元素的下标，将其指定为新的父文件夹，然后查找子文件夹
                a = i;
                ans.add(folder[a]);
            }
        }
        return ans;//返回存储父文件夹的List
    }
   
}

图解：

如图是排序后的数组，第一次flag为0，标记的父文件夹为0号元素。然后比较1号和0号元素，判断1号是否时0号的子文件夹，结果为 是 。继续判断2号元素，2号不是0号的子文件夹，于是存储2号元素代表的父文件夹地址，将标记flag变为2，然后往后查找……