LeetCode 1233. 删除子文件夹

Categories:

题目描述
思路分析
1. 解法一：排序 + 前缀判断（推荐）
相似题目

题目描述

✅ 1233. 删除子文件夹

思路分析

解法一：排序 + 前缀判断（推荐）

核心思路：

将所有文件夹按字典序排序。

若当前路径不是上一个保留路径的子路径，则保留。

子路径判定：curr 以 prev + "/" 为前缀。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示文件夹数量。

空间复杂度：O(1)，除结果外仅使用常数额外空间。

class Solution {
    public List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);
        List<String> res = new ArrayList<>();

        String prev = "";
        for (String cur : folder) {
            if (prev.isEmpty() || !cur.startsWith(prev + "/")) {
                res.add(cur);
                prev = cur;
            }
        }

        return res;
    }
}

func removeSubfolders(folder []string) []string {
	sort.Strings(folder)
	res := make([]string, 0)
	prev := ""

	for _, cur := range folder {
		if prev == "" || !strings.HasPrefix(cur, prev+"/") {
			res = append(res, cur)
			prev = cur
		}
	}

	return res
}

相似题目

题目	难度	考察点
820. 单词的压缩编码	中等	排序 + 前缀
648. 单词替换	中等	Trie
676. 实现一个魔法字典	中等	Trie
1233. 删除子文件夹	中等	排序
472. 连接词	困难	Trie

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/23362247