파일 시스템에서 하위 폴더 제거

1233. 파일 시스템에서 하위 폴더 제거

난이도:중

주제: 배열, 문자열, 깊이 우선 검색, Trie

폴더 폴더 목록이 주어지면 해당 폴더의 하위 폴더를 모두 제거한 후 폴더를 반환합니다. 어떤 순서로든 답변을 보내실 수 있습니다.

폴더[i]가 다른 폴더[j] 내에 있으면 해당 폴더를 하위 폴더라고 합니다. 폴더[j]의 하위 폴더는 폴더[j]로 시작하고 그 뒤에 "/"가 와야 합니다. 예를 들어 "/a/b"는 "/a"의 하위 폴더이지만 "/b"는 "/a/b/c"의 하위 폴더가 아닙니다.

경로 형식은 '/' 다음에 하나 이상의 영어 소문자가 오는 형식의 하나 이상의 연결된 문자열입니다.

• 예를 들어 "/leetcode" 및 "/leetcode/problems"는 유효한 경로이지만 빈 문자열 및 "/"는 유효하지 않습니다.

예 1:

• 입력: 폴더 = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
• 출력: ["/a","/c/d","/c/f"]
• 설명: 폴더 "/a/b"는 "/a"의 하위 폴더이고 "/c/d/e"는 파일 시스템의 "/c/d" 폴더 안에 있습니다.

예 2:

• 입력: 폴더 = ["/a","/a/b/c","/a/b/d"]
• 출력: ["/a"]
• 설명: "/a/b/c" 및 "/a/b/d" 폴더는 "/a"의 하위 폴더이므로 제거됩니다.

예 3:

• 입력: 폴더 = ["/a/b/c","/a/b/ca","/a/b/d"]
• 출력: ["/a/b/c","/a/b/ca","/a/b/d"]

제약조건:

• 1 4
• 2
• 폴더[i]에는 소문자와 '/'만 포함됩니다.
• 폴더[i]는 항상 '/' 문자로 시작합니다.
• 각 폴더 이름은 고유합니다.

힌트:

1. 폴더를 사전순으로 정렬하세요.
2. 현재 요소를 배열에 삽입한 다음 하위 폴더를 모두 제거할 때까지 반복하고 요소가 더 이상 남지 않을 때까지 반복합니다.

해결책:

정렬과 문자열 비교를 조합하여 활용할 수 있습니다. 아래 단계에서는 PHP의 솔루션을 간략하게 설명합니다.

1. 사전순으로 폴더 정렬: 사전순으로 폴더 경로를 정렬하면 모든 하위 폴더가 즉시 상위 폴더를 따르게 됩니다. 예를 들어 정렬된 목록에서 "/a" 다음에 "/a/b"가 표시되므로 하위 폴더 관계를 쉽게 확인할 수 있습니다.

2. 하위 폴더 식별 및 필터링: 정렬된 목록을 반복하여 현재 폴더 경로가 이전에 추가된 경로의 하위 폴더인지 확인할 수 있습니다. 그렇다면 건너뜁니다. 그렇지 않은 경우 결과 목록에 추가합니다.

3. PHP에서 솔루션 구현: 결과 목록에 마지막으로 추가된 폴더 경로를 추적합니다. 현재 폴더가 이 마지막 폴더로 시작하고 바로 뒤에 /가 오면 하위 폴더이므로 무시해야 합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 1233. 파일 시스템에서 하위 폴더 제거

<?php /**
 * @param String[] $folder
 * @return String[]
 */
function removeSubfolders($folders) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$folder1 = ["/a","/a/b","/c/d","/c/d/e","/c/f"];
$folder2 = ["/a","/a/b/c","/a/b/d"];
$folder3 = ["/a/b/c","/a/b/ca","/a/b/d"];

print_r(removeSubfolders($folder1)); // Output: ["/a","/c/d","/c/f"]
print_r(removeSubfolders($folder2)); // Output: ["/a"]
print_r(removeSubfolders($folder3)); // Output: ["/a/b/c","/a/b/ca","/a/b/d"]
?>

설명:

1. 정렬: sort() 함수는 폴더를 사전순으로 정렬합니다. 하위 폴더가 상위 폴더를 직접 따르기 때문에 하위 폴더 관계를 더 쉽게 찾을 수 있습니다.

2. 각 폴더를 반복:

   • 결과가 비어 있거나(첫 번째 반복) 현재 폴더 경로가 마지막으로 추가된 폴더와 / 뒤에 오는 폴더로 시작하지 않는 경우 하위 폴더가 아니며 결과 배열에 추가됩니다.
   • 마지막 폴더 경로로 시작하고 바로 뒤에 /가 있으면 하위 폴더이므로 결과에 추가하는 것을 건너뜁니다.

3. 결과: 이 함수는 하위 폴더를 제외하고 루트 폴더만 포함하는 결과를 반환합니다.

이 접근 방식은 정렬 단계로 인해 O(n log n)의 시간 복잡도로 효율적이며 선형 스캔은 O(n ) 문제의 제약 내에서 더 큰 입력을 처리하는 데 적합한 솔루션입니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 파일 시스템에서 하위 폴더 제거의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!