문제

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.

If a folder[i] is located within another folder[j], it is called a sub-folder of it. A sub-folder of folder[j] must start with folder[j], followed by a "/". For example, "/a/b" is a sub-folder of "/a", but "/b" is not a sub-folder of "/a/b/c".

The format of a path is one or more concatenated strings of the form: '/' followed by one or more lowercase English letters.

For example, "/leetcode" and "/leetcode/problems" are valid paths while an empty string and "/" are not.

요약

String parsing하는 문제이다. 그냥 /단위로 자르면된다.

풀이

데이터가 40000개밖에 없고 글자수도 최대 100자라 충분이 전탐해도 될것 같다

코드

class Solution {
    public List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);
        Set<String> set = new HashSet<>();
        for (String f : folder) {
            addOrIgnore(set, f);
        }
        return set.stream().toList();
    }

    private void addOrIgnore(Set<String> set, String f) {
        int idx = f.length();
        int max = idx;
        while (idx > 0) {
            char c = idx != max ? f.charAt(idx) : '/';
            String s = f.substring(0, idx);
            if (c == '/') {
                if (set.contains(s)) {
                    return;
                }
            }
            idx --;
        }
        set.add(f);
    }
}

풀이 시간

10분

체감 난이도

easy